發(fā)布時間：2018-06-19 13:07

  本文選題：與工藝規(guī)劃集成的調(diào)度問題 + 混合整數(shù)線性規(guī)劃模型��； 參考：《華中科技大學(xué)》2016年博士論文

【摘要】：工藝規(guī)劃和車間調(diào)度是制造系統(tǒng)中非常重要的兩個組成部分。工藝規(guī)劃是零件從設(shè)計到加工中重要的一環(huán),它通過確定各個工序的先后加工關(guān)系、加工的設(shè)備及相關(guān)參數(shù)來生成可行的加工方案;車間調(diào)度是通過合理安排各個工序在機器上的順序使得某些指標(biāo)(如最大完工時間)得到優(yōu)化。當(dāng)前大多數(shù)制造企業(yè)中這兩個子系統(tǒng)被認(rèn)為是兩個獨立的系統(tǒng)。然而,將工藝規(guī)劃與車間調(diào)度問題進行集成能極大地提高制造系統(tǒng)的效率。因此,工藝規(guī)劃與調(diào)度集成(integrated process 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)不確定條件下IPPS問題的高效求解方法。首先,本文在充分研究已有模型的基礎(chǔ)上,首次建立基于網(wǎng)絡(luò)圖的工藝規(guī)劃與調(diào)度集成式問題混合整數(shù)線性規(guī)劃模型。提出一種新穎的基于網(wǎng)絡(luò)圖建模策略,通過引入合適的約束,克服了現(xiàn)有模型的缺陷。為測試模型的正確性,對小規(guī)模及大規(guī)�；鶞�(zhǔn)測試實例進行了測試,實驗結(jié)果表明提出的模型可以得到正確的調(diào)度結(jié)果。然而,受到IPPS問題復(fù)雜性的影響,對于大規(guī)模問題在計算時間上無法令人滿意。其次,針對問題的復(fù)雜性,采用元啟發(fā)式算法對IPPS單目標(biāo)問題進行求解。以最大工期(makespan)最小化為目標(biāo),把遺傳算法與變鄰域搜索(variable neighborhood search, VNS)有機結(jié)合以避免算法陷入局部最優(yōu),設(shè)計一種新穎的混合遺傳算法求解IPPS問題。在混合算法中,提出一種新的編碼方案及其相應(yīng)的選擇交叉方法,并引入兩種高效的鄰域結(jié)構(gòu)提高變鄰域局部搜索的效率。采用基準(zhǔn)測試實例驗證提出的算法,獲得的最大工期值遠(yuǎn)優(yōu)于目前已有文獻中的結(jié)果。對于Kim的基準(zhǔn)測試實例,在24個問題中有12個得到改進,成為當(dāng)前最優(yōu)解,且有17個實例達到理論最優(yōu)值(下界值)。再次,由于在實際生產(chǎn)中多目標(biāo)問題普遍存在,對多目標(biāo)IPPS問題進行了研究。針對實際生產(chǎn)常遇到的三個指標(biāo)：最大工期(makespan)、最大機器載荷(maximum machine workload, MMW)及總機器載荷(total workload of machines, TWM),在單目標(biāo)算法的基礎(chǔ)上,本文設(shè)計一種多目標(biāo)群體智能算法求解IPPS問題。在提出的多目標(biāo)群體智能算法中,引入了局部搜索方法以尋求更優(yōu)的非支配解。不同于其他采用局部搜索的多目標(biāo)算法,本文提出的局部搜索算法針對三個優(yōu)化指標(biāo)逐個進行優(yōu)化,以獲得更優(yōu)Pareto前沿解。此外,在得到了最優(yōu)Pareto前沿后,采用TOPSIS方法從一組非支配解中得到最令人滿意的解。采用基準(zhǔn)測試實例測試了提出的算法,并與NSGA-II算法進行了對比,測試結(jié)果驗證提出的多目標(biāo)算法的有效性。然后,本文對動態(tài)環(huán)境下的IPPS問題進行研究。當(dāng)前,大部分文獻中研究的IPPS問題是靜態(tài)的,即認(rèn)為所有工件允許加工時間為零時刻。但在實際生產(chǎn)中不確定因素(如工件隨機到達)總是存在的。因此,靜態(tài)IPPS問題的求解結(jié)果很難適應(yīng)實際生產(chǎn)環(huán)境。本文對IPPS問題的事件驅(qū)動再調(diào)度及周期性再調(diào)度進行了研究。計算結(jié)果表明,調(diào)度間隔的長度、新到達工件的個數(shù)及車間利用率對調(diào)度性能有重要的影響。最后,在理論研究基礎(chǔ)上,開發(fā)了集成工藝規(guī)劃的車間調(diào)度原型系統(tǒng),并在最后一章對全文進行了總結(jié),給出了進一步的研究方向。
[Abstract]:This paper presents a novel hybrid genetic algorithm to solve IPPS problem . On the basis of single objective algorithm , we design a multi - target group intelligent algorithm to solve the problem of IPPS . In this paper , we study the problem of IPPS in dynamic environment .
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP18;TB497
，

本文編號：2039990