異順序車間作業(yè)計(jì)劃的混合調(diào)度算法.pdf

1、Job-shop調(diào)度問題是生產(chǎn)調(diào)度領(lǐng)域的一個(gè)熱點(diǎn)、難點(diǎn)，是許多實(shí)際生產(chǎn)調(diào)度問題的典型調(diào)度簡(jiǎn)化模型，是一類典型的NP-hard問題，對(duì)它的研究具有重要的理論意義和應(yīng)用價(jià)值。 針對(duì)以最小化最大完工時(shí)間（Makespan）為目標(biāo)的Job-shop問題，本文提出一種基于禁忌搜索（TS）和移動(dòng)瓶頸過程（SB）的混合啟發(fā)式算法HTS_SB。具體研究?jī)?nèi)容和成果如下： （1）禁忌搜索的性能與初始解有密切關(guān)系，從優(yōu)質(zhì)解和劣質(zhì)解出發(fā)進(jìn)行的搜

2、索有時(shí)在性能上的差別是相當(dāng)可觀的；針對(duì)這一特性，本文提出以移動(dòng)瓶頸過程來產(chǎn)生優(yōu)質(zhì)的初始解，為HTS_SB算法的主體過程禁忌搜索奠定基礎(chǔ)。 （2）鄰域結(jié)構(gòu)對(duì)禁忌搜索的性能影響很大，一個(gè)好的鄰域結(jié)構(gòu)應(yīng)盡量避免對(duì)無用解的搜索，并要對(duì)搜索范圍進(jìn)行很好的控制，搜索范圍太大或太小都會(huì)對(duì)搜索過程產(chǎn)生負(fù)面影響。鑒于此，本文在已提出的關(guān)于鄰域結(jié)構(gòu)的理論證明和結(jié)論的基礎(chǔ)上，結(jié)合現(xiàn)有高效的鄰域結(jié)構(gòu)，提出一種新的鄰域結(jié)構(gòu)，同時(shí)采用動(dòng)態(tài)的禁忌列表，提高算

3、法的搜索能力，將鄰域搜索算法的復(fù)雜度降低。 （3）對(duì)產(chǎn)生初始解的移動(dòng)瓶頸過程主體Schrage算法進(jìn)行改進(jìn)，引入擾亂因子，打破Schrage算法原有的優(yōu)先級(jí)順序，將其從精確算法演變?yōu)榻扑惴?，從而搜索更?yōu)的初始解。 （4）如在移動(dòng)瓶頸過程中采用Carlier，則可能存在不可行解的問題。針對(duì)這個(gè)特點(diǎn)，對(duì)移動(dòng)瓶頸算法進(jìn)行修改，在對(duì)單機(jī)調(diào)度時(shí)用Schrage算法來代替Carlier算法，避免產(chǎn)生不可行解。 將HTS_S