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

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

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