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

【摘要】：工藝規(guī)劃和車間調(diào)度是制造系統(tǒng)中非常重要的兩個(gè)組成部分。工藝規(guī)劃是零件從設(shè)計(jì)到加工中重要的一環(huán),它通過確定各個(gè)工序的先后加工關(guān)系、加工的設(shè)備及相關(guān)參數(shù)來生成可行的加工方案;車間調(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 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問題：對(duì)規(guī)模稍大的問題,啟發(fā)式算法和元啟發(fā)式算法能在較短時(shí)間獲得較優(yōu)解,成為較好的選擇。本文在深入探索與工藝規(guī)劃集成的調(diào)度問題的基礎(chǔ)上,建立相應(yīng)的數(shù)學(xué)模型,研究單目標(biāo)、多目標(biāo)和動(dòng)態(tài)不確定條件下IPPS問題的高效求解方法。首先,本文在充分研究已有模型的基礎(chǔ)上,首次建立基于網(wǎng)絡(luò)圖的工藝規(guī)劃與調(diào)度集成式問題混合整數(shù)線性規(guī)劃模型。提出一種新穎的基于網(wǎng)絡(luò)圖建模策略,通過引入合適的約束,克服了現(xiàn)有模型的缺陷。為測試模型的正確性,對(duì)小規(guī)模及大規(guī)�；鶞�(zhǔn)測試實(shí)例進(jìn)行了測試,實(shí)驗(yàn)結(jié)果表明提出的模型可以得到正確的調(diào)度結(jié)果。然而,受到IPPS問題復(fù)雜性的影響,對(duì)于大規(guī)模問題在計(jì)算時(shí)間上無法令人滿意。其次,針對(duì)問題的復(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)測試實(shí)例驗(yàn)證提出的算法,獲得的最大工期值遠(yuǎn)優(yōu)于目前已有文獻(xiàn)中的結(jié)果。對(duì)于Kim的基準(zhǔn)測試實(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)算法的基礎(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)測試實(shí)例測試了提出的算法,并與NSGA-II算法進(jìn)行了對(duì)比,測試結(jié)果驗(yàn)證提出的多目標(biāo)算法的有效性。然后,本文對(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)度間隔的長度、新到達(dá)工件的個(gè)數(shù)及車間利用率對(duì)調(diào)度性能有重要的影響。最后,在理論研究基礎(chǔ)上,開發(fā)了集成工藝規(guī)劃的車間調(diào)度原型系統(tǒng),并在最后一章對(duì)全文進(jìn)行了總結(jié),給出了進(jìn)一步的研究方向。
[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é)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18;TB497
，

本文編號(hào)：2039990