基于網(wǎng)絡(luò)圖與工藝規(guī)劃集成的車間調(diào)度.pdf

1、工藝規(guī)劃和車間調(diào)度是制造系統(tǒng)中非常重要的兩個(gè)組成部分。工藝規(guī)劃是零件從設(shè)計(jì)到加工中重要的一環(huán)，它通過確定各個(gè)工序的先后加工關(guān)系、加工的設(shè)備及相關(guān)參數(shù)來(lái)生成可行的加工方案；車間調(diào)度是通過合理安排各個(gè)工序在機(jī)器上的順序使得某些指標(biāo)（如最大完工時(shí)間）得到優(yōu)化。當(dāng)前大多數(shù)制造企業(yè)中這兩個(gè)子系統(tǒng)被認(rèn)為是兩個(gè)獨(dú)立的系統(tǒng)。然而，將工藝規(guī)劃與車間調(diào)度問題進(jìn)行集成能極大地提高制造系統(tǒng)的效率。因此，工藝規(guī)劃與調(diào)度集成（integrated process

2、planning and scheduling, IPPS）問題受到越來(lái)越多研究人員的關(guān)注。
　　傳統(tǒng)的作業(yè)車間調(diào)度是復(fù)雜的NP-hard組合優(yōu)化問題，與工藝規(guī)劃集成的車間調(diào)度更增加了問題的求解難度。至今為止，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法只能夠解決小規(guī)模IPPS問題；對(duì)規(guī)模稍大的問題，啟發(fā)式算法和元啟發(fā)式算法能在較短時(shí)間獲得較優(yōu)解，成為較好的選擇。本文在深入探索與工藝規(guī)劃集成的調(diào)度問題的基礎(chǔ)上，建立相應(yīng)的數(shù)學(xué)模型，研究單目標(biāo)、多目標(biāo)和動(dòng)態(tài)不

3、確定條件下IPPS問題的高效求解方法。
　　首先，本文在充分研究已有模型的基礎(chǔ)上，首次建立基于網(wǎng)絡(luò)圖的工藝規(guī)劃與調(diào)度集成式問題混合整數(shù)線性規(guī)劃模型。提出一種新穎的基于網(wǎng)絡(luò)圖建模策略，通過引入合適的約束，克服了現(xiàn)有模型的缺陷。為測(cè)試模型的正確性，對(duì)小規(guī)模及大規(guī)?；鶞?zhǔn)測(cè)試實(shí)例進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果表明提出的模型可以得到正確的調(diào)度結(jié)果。然而，受到IPPS問題復(fù)雜性的影響，對(duì)于大規(guī)模問題在計(jì)算時(shí)間上無(wú)法令人滿意。
　　其次，針對(duì)問題的

4、復(fù)雜性，采用元啟發(fā)式算法對(duì) IPPS單目標(biāo)問題進(jìn)行求解。以最大工期（makespan）最小化為目標(biāo)，把遺傳算法與變鄰域搜索（variable neighborhood search, VNS）有機(jī)結(jié)合以避免算法陷入局部最優(yōu)，設(shè)計(jì)一種新穎的混合遺傳算法求解IPPS問題。在混合算法中，提出一種新的編碼方案及其相應(yīng)的選擇交叉方法，并引入兩種高效的鄰域結(jié)構(gòu)提高變鄰域局部搜索的效率。采用基準(zhǔn)測(cè)試實(shí)例驗(yàn)證提出的算法，獲得的最大工期值遠(yuǎn)優(yōu)于目前已有文

5、獻(xiàn)中的結(jié)果。對(duì)于 Kim的基準(zhǔn)測(cè)試實(shí)例，在24個(gè)問題中有12個(gè)得到改進(jìn)，成為當(dāng)前最優(yōu)解，且有17個(gè)實(shí)例達(dá)到理論最優(yōu)值（下界值）。
　　再次，由于在實(shí)際生產(chǎn)中多目標(biāo)問題普遍存在，對(duì)多目標(biāo)IPPS問題進(jìn)行了研究。針對(duì)實(shí)際生產(chǎn)常遇到的三個(gè)指標(biāo)：最大工期（makespan）、最大機(jī)器載荷（maximum machine workload, MMW）及總機(jī)器載荷（total workload of machines, TWM），在單目標(biāo)算法

6、的基礎(chǔ)上，本文設(shè)計(jì)一種多目標(biāo)群體智能算法求解 IPPS問題。在提出的多目標(biāo)群體智能算法中，引入了局部搜索方法以尋求更優(yōu)的非支配解。不同于其他采用局部搜索的多目標(biāo)算法，本文提出的局部搜索算法針對(duì)三個(gè)優(yōu)化指標(biāo)逐個(gè)進(jìn)行優(yōu)化，以獲得更優(yōu)Pareto前沿解。此外，在得到了最優(yōu)Pareto前沿后，采用TOPSIS方法從一組非支配解中得到最令人滿意的解。采用基準(zhǔn)測(cè)試實(shí)例測(cè)試了提出的算法，并與NSGA-II算法進(jìn)行了對(duì)比，測(cè)試結(jié)果驗(yàn)證提出的多目標(biāo)算法的

7、有效性。
　　然后，本文對(duì)動(dòng)態(tài)環(huán)境下的IPPS問題進(jìn)行研究。當(dāng)前，大部分文獻(xiàn)中研究的IPPS問題是靜態(tài)的，即認(rèn)為所有工件允許加工時(shí)間為零時(shí)刻。但在實(shí)際生產(chǎn)中不確定因素（如工件隨機(jī)到達(dá)）總是存在的。因此，靜態(tài) IPPS問題的求解結(jié)果很難適應(yīng)實(shí)際生產(chǎn)環(huán)境。本文對(duì) IPPS問題的事件驅(qū)動(dòng)再調(diào)度及周期性再調(diào)度進(jìn)行了研究。計(jì)算結(jié)果表明，調(diào)度間隔的長(zhǎng)度、新到達(dá)工件的個(gè)數(shù)及車間利用率對(duì)調(diào)度性能有重要的影響。
　　最后，在理論研究基礎(chǔ)上，開