作業(yè)車間調度問題的高效率算法.pdf

1、作業(yè)車間調度問題是公認的最難的組合優(yōu)化問題之一，也是一個典型的NP 難度問題。研究作業(yè)車間調度問題具有很高的理論價值。同時，作業(yè)車間調度問題是實際工業(yè)生產調度問題的抽象表述，不僅可以應用于生產調度方面，而且可以應用在經濟管理、交通運輸以及網絡通訊等各個領域。所以，對作業(yè)車間調度問題的研究也具有很高的實際意義。
　　 數十年來，國內外的許多學者對作業(yè)車間調度問題進行了深入研究，提出了許多算法。用精確算法求解該問題時，計算時間隨著問

2、題規(guī)模的增大呈指數級增加，其實際價值并不大。因此，設計高效的求解作業(yè)車間調度問題的啟發(fā)式算法成為當前研究的重點。
　　 針對作業(yè)車間調度問題，提出了一種高效的解的可行性判定算法T。用該算法對8組不同規(guī)模的國際標準算例進行了測試，并與基于深度優(yōu)先遍歷思想的判定算法DFS算法進行了比較。實驗結果表明，T算法的效率比DFS算法要高很多。
　　 設計了一種新的鄰域結構和一種有效的搜索機制，形成了混合鄰域搜索算法DSP。該算法能夠