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

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

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

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

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

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

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

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