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

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

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

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

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

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