具有成組約束的柔性流水車間作業(yè)計劃制定的啟發(fā)式算法.pdf

1、具有成組約束的柔性流水車間調(diào)度問題普遍存在于離散制造業(yè)，對其進行研究具有重要理論意義和工程實用價值，因此吸引著越來越多研究人員對其進行研究。具有成組約束的柔性流水車間調(diào)度問題是傳統(tǒng)調(diào)度問題的一種擴展，根據(jù)出現(xiàn)成組位置的不同可分為三類子問題:前、中、后成組約束的柔性流水車間調(diào)度問題。該類問題是柔性流水車間調(diào)度問題和成組問題相結合的混合車間調(diào)度問題，因此屬于NP難問題。對于NP難問題，由于目標解的搜索涉及解空間的組合爆炸，所以通常不能有效地

2、求出問題的最優(yōu)解。線性規(guī)劃、分支定界等傳統(tǒng)方法對于稍大規(guī)模的車間調(diào)度問題的求解無能為力，因此，通常使用啟發(fā)式算法求解該類問題。所以，本文研究了啟發(fā)式算法在具有成組約束的柔性流水車間調(diào)度中的應用，取得的主要研究成果如下:
　　 1.針對以最少化最大完工時間為目標的具有前成組約束的兩階段柔性流水車間調(diào)度問題，建立了其數(shù)學模型;通過對問題的結構進行分析，提出了一種啟發(fā)式算法H';對H'算法分析后，給出了H'算法的時間復雜度和最壞情況值

3、;為了驗證H'算法的效果，通過設計大量仿真算例和與其它三種改進后的經(jīng)典啟發(fā)式算法進行比較，結果表明H'算法對于求解具有前成組約束的兩階段柔性流水車間調(diào)度問題的優(yōu)越性;最后，基于H'算法，提出一種啟發(fā)式算法MH’求解具有前成組約束的多階段柔性流水車間調(diào)度問題。
　　 2.針對以總拖期量最少為目標的具有后成組約束的兩階段柔性流水車間調(diào)度問題，建立了其數(shù)學模型;通過對問題的分析，給出一條調(diào)度優(yōu)勢準則;基于該調(diào)度優(yōu)勢準則，提出了一種啟發(fā)

4、式算法EL;通過對EL算法進行分析，給出其時間復雜度和最壞情況值;為了驗證EL算法的有效性，設計了該類問題的仿真算例，通過對算例的仿真及結果分析表明了算法的有效性和EL調(diào)度規(guī)則在求解該類問題時的優(yōu)越性;最后，基于EL算法，提出一種啟發(fā)式算法MEL求解具有后成組約束的多階段柔性流水車間調(diào)度問題。
　　 3.研究了求解目標為最少化最大完工時間的具有中成組約束的三階段柔性流水車間調(diào)度問題，建立了該問題的數(shù)學模型;通過對問題的結構分析，

5、提出了10種啟發(fā)式算法，并給出了該10種啟發(fā)式算法的時間復雜度;通過對問題進行分析，給出了該問題的四個下界;通過對該10種啟發(fā)式算法進行分析，給出了其中9個啟發(fā)式算法的最壞情況值;為了驗證該10種啟發(fā)式算法的求解效果，設計了仿真實驗，仿真結果表明SP.JH-MJ算法對于求解具有中成組約束的三階段柔性流水車間調(diào)度問題的優(yōu)越性;最后基于SP.JH-MJ算法，提出了一種啟發(fā)式算法MJL求解具有中成組約束的多階段柔性流水車間調(diào)度問題。