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

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

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

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