基于約束滿足的改進(jìn)蟻群算法在車間調(diào)度中的應(yīng)用研究.pdf

1、調(diào)度(Scheduling)研究的問題是將有限的資源實(shí)行任務(wù)的時(shí)間分配，以實(shí)現(xiàn)某性能指標(biāo)最優(yōu)。而現(xiàn)實(shí)中的調(diào)度問題多為復(fù)雜的組合優(yōu)化問題，如車間調(diào)度問題(Job-shop Scheduling Problem，JSP)即為典型的NP難問題，在其復(fù)雜多項(xiàng)式時(shí)間內(nèi)難以找到最優(yōu)解。因車間調(diào)度問題的研究具有理論和實(shí)踐意義，所以一直是調(diào)度問題中研究的熱點(diǎn)，也是難點(diǎn)，近年來對JSP的研究主要集中于利用現(xiàn)代智能算法以及各種改進(jìn)的混合算法求近似解。本文利

2、用新興的蟻群優(yōu)化算法，結(jié)合約束滿足技術(shù)對車間調(diào)度問題進(jìn)行求解。
　　 蟻群優(yōu)化算法(Ant Colony Optimization Algorithm，ACO)因其魯棒性、正反饋性、并行性等優(yōu)點(diǎn)，已經(jīng)在求解很多組合優(yōu)化問題方面取得了良好的效果，算法的效率也很高；但是蟻群算法也存在著收斂慢、易停滯的缺點(diǎn)。本文在充分利用蟻群算法優(yōu)點(diǎn)的前提下，對蟻群算法進(jìn)行改進(jìn)，采用全局和局部信息素更新相結(jié)合的信息素更新策略以避免算法過早停滯；而對于

3、收斂慢的缺點(diǎn)，采用約束滿足技術(shù)修剪搜索空間，以加快搜索速度，提高算法效率。另外，蟻群算法中各參數(shù)的選取對算法的性能也有較大的影響，本文也給出了詳細(xì)的分析。
　　 約束滿足(Constraint Satisfaction)作為求解大規(guī)模組合優(yōu)化問題的方法之一，能對搜索空間進(jìn)行修剪，從而大大減少搜索的次數(shù)和時(shí)間。一致性預(yù)處理技術(shù)和約束傳播技術(shù)可以在搜索過程中動態(tài)地排除不符合約束條件的區(qū)域，使搜索.過程不必遍歷所有的變量和賦值，只須保

4、持局部一致性。
　　 混合算法充分利用二者的優(yōu)點(diǎn)，約束滿足技術(shù)的使用使得蟻群算法的效率有了更進(jìn)一步的提高，從而很快地找到可行解和最佳方案。本文通過實(shí)驗(yàn)驗(yàn)證了混合算法的可行性，并通過標(biāo)準(zhǔn)的車間調(diào)度實(shí)例進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果的分析比較（和其他算法進(jìn)行比較）證明，改進(jìn)的混合算法不但具有可行性，而且具有高效性。另外，本文還實(shí)現(xiàn)了實(shí)際生產(chǎn)調(diào)度過程中并行機(jī)存在時(shí)的調(diào)度情況，使算法的求解更符合實(shí)際生產(chǎn)的要求。
　　 最后，本文利用C+