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

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

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