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

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

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