本文關鍵詞：有模具限制的并行機臺調度問題研究

  更多相關文章： 并行機器 最大完工時間 模具限制 啟發(fā)式算法

【摘要】：在基于工業(yè)4.0概念下的智能制造領域,車間調度問題的研究愈加受到制造企業(yè)的關注。特別是在科技含量高、自動化程度明顯的生產車間中,針對制造過程的優(yōu)化是提高生產效率、減少成本和保證產能的重要手段。隨著生產方式的不斷改進,基于現(xiàn)實生產中的約束提出的調度問題更加貼近生產實際情況,對于此類問題的研究為企業(yè)在生產調度和排程方面提供了可靠依據和參考。本文主要研究了有模具限制的等效并行機器最小化最大完工時間問題。在半導體車間中,晶圓曝光操作需要在特殊的并行設備上通過光罩輔助加工,光罩需要與晶圓對應使用且數(shù)量較少。在這樣的情況下,制造者需要對晶圓的加工順序做出合理安排,優(yōu)化生產流程,提高機器的利用率,達到最小化最大完工時間的目的。并行機(Parallel Machine)調度問題的研究在理論和實際中都具有重要意義。在理論研究方面,并行機調度問題不僅是單機問題的衍生問題,也是混合流水車間問題的特殊情況;在實際生產方面,并行機調度問題頻繁出現(xiàn)在工業(yè)流程中,同時其研究方法在多階段系統(tǒng)的分解程序中也具有廣泛應用。等效并行機器最小化最大完工時間問題可以表示為maxP||C,在無任何約束的情況下,即使是在兩臺并行機器的生產環(huán)境中,也已經被證明為NP-hard問題。首先,本文針對有模具限制的并行機器調度問題,建立了包含工件位置約束和加工條件約束的數(shù)學模型,初步得到小規(guī)模問題中的最優(yōu)解。此外,通過對問題約束的簡化,在maxP||C問題的數(shù)學模型基礎上,得到了問題下界的計算方法;其次,在對問題特點的分析及歸納的基礎上,提出了兩種啟發(fā)式演算法,試圖通過這兩種方式達到高效解決大規(guī)模問題的目的,兩種啟發(fā)式演算法具有各自的特點。第一,通過數(shù)學證明的方法,提出了兩種算法的worst case,得到了兩種啟發(fā)式演算法得到的解與最優(yōu)解之間的差距估計。第二,針對算法的偽代碼進行了分析和計算,得到了兩種算法的復雜度,對算法的性能及求解效率做出了比較;最后,為了證明所提出的兩種啟發(fā)式演算法的求解效果,對離散的粒子群優(yōu)化算法以及變領域優(yōu)化算法做出了改進。一是提出了更加適合題目類型的編碼方式,對于粒子群優(yōu)化算法采用多維度的二進制編碼方式,迭代更新時保留了局部最優(yōu)序列的特點。二是初始解的產生方式采用了所提出的兩種啟發(fā)式算法,這種初始解的產生方式使算法在較短的時間內就可以取得較優(yōu)的解。實驗分析證明:提出的兩種啟發(fā)式算法DMLPT和TLPT以及改進的兩種萬用啟發(fā)式算法可以得到問題的較優(yōu)解。尤其對于兩種啟發(fā)式算法DMLPT和TLPT算法的比較分析中發(fā)現(xiàn),兩種算法的求解效率和質量具有較大優(yōu)勢,其中DMLPT算法在大規(guī)模問題中表現(xiàn)出求解時間短、與最優(yōu)解差距小等特點。
【關鍵詞】：并行機器 最大完工時間 模具限制 啟發(fā)式算法
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TB497
【目錄】：

• 摘要4-6
• Abstract6-10
• 第一章 緒論10-20
• 1.1 研究背景及意義10-12
• 1.2 國內外研究現(xiàn)狀12-16
• 1.2.1 國外研究現(xiàn)狀12-14
• 1.2.2 國內研究現(xiàn)狀14-16
• 1.3 主要的研究內容及結構安排16-20
• 1.3.1 主要研究內容16-18
• 1.3.2 本文的結構安排18-20
• 第二章 數(shù)學模型與啟發(fā)式算法20-42
• 2.1 問題的背景與描述20-22
• 2.2 混合整數(shù)規(guī)劃模型的建立22-27
• 2.2.1 符號及變量的定義22-23
• 2.2.2 數(shù)學模型的建立23-27
• 2.3 啟發(fā)式算法建立及分析比較27-40
• 2.3.1 LPT規(guī)則概述27-29
• 2.3.2 TLPT算法的建立29-32
• 2.3.3 TLPT算法的性能分析32-35
• 2.3.4 DMLPT算法的建立35-38
• 2.3.5 DMLPT算法的性能分析38-40
• 2.4 本章小結40-42
• 第三章 萬用啟發(fā)式演算法的設計42-60
• 3.1 萬用啟發(fā)式算法概述42-44
• 3.2 粒子群優(yōu)化算法44-52
• 3.2.1 粒子群優(yōu)化算法的原理44-48
• 3.2.2 改進的離散粒子群算法的建立48-52
• 3.3 變鄰域搜索算法52-58
• 3.3.1 變鄰域搜索算法的原理52-55
• 3.3.2 改進的變鄰域搜索算法的建立55-58
• 3.4 本章小結58-60
• 第四章 實驗分析及應用實例60-74
• 4.1 實驗的目的及應用背景60-61
• 4.2 實驗的環(huán)境及參數(shù)設置61-62
• 4.3 實驗的結果及對比分析62-72
• 4.4 本章小結72-74
• 第五章 結論與展望74-76
• 5.1 全文結論74-75
• 5.2 未來展望75-76
• 參考文獻76-82
• 作者簡介82-84
• 攻讀學位期間主要從事的科研工作84-86
• 致謝86

【相似文獻】

中國期刊全文數(shù)據庫 前10條

1 劉琳;谷寒雨;席裕庚;;工件到達時間未知的動態(tài)車間滾動重調度[J];機械工程學報;2008年05期

2 郭艷東;黃敏;王慶;;鎖定初始調度的緊急工作單機重調度問題[J];東北大學學報(自然科學版);2013年05期

3 姜洋;孫偉;丁秋雷;張旭;;考慮行為主體的單機調度干擾管理模型[J];機械工程學報;2013年14期

4 席裕庚,王長軍;控制、規(guī)劃和調度問題中的博弈論應用[J];中國計量學院學報;2005年01期

5 徐群嶺;;基于免疫優(yōu)化的公交駕駛員調度問題[J];計算機工程;2010年24期

6 喻道遠;史登松;劉盛強;張三強;;帶模糊排序的移動瓶頸法求解不確定調度問題[J];機械制造;2011年02期

7 劉鵬;周曉曄;衣娜;;帶有減少線性惡化效應的雙代理調度問題[J];系統(tǒng)工程學報;2011年03期

8 劉曉東;陳英武;龍運軍;賀仁杰;李菊芳;;同型機在線調度問題研究進展[J];計算機集成制造系統(tǒng);2012年03期

9 姚君遺，楊善林，左春榮;基于實例FMS的AGV調度數(shù)學模型與算法[J];合肥工業(yè)大學學報(自然科學版);1995年01期

10 董平;機器調度問題及求解方法[J];物流技術與應用;1997年01期

中國重要會議論文全文數(shù)據庫 前10條

1 李建更;涂凍生;馬海濤;;單機拖后時間總和問題交付期擾動時最優(yōu)調度不變范圍的一種求法[A];第十九屆中國控制會議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費用最小的多機調度問題[A];1995中國控制與決策學術年會論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調度的復雜性及解決方法[A];’2004計算機應用技術交流會議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調度[A];1996中國控制與決策學術年會論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調度問題研究[A];2006年首屆ICT大會信息、知識、智能及其轉換理論第一次高峰論壇會議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時間的單機調度問題[A];1996中國控制與決策學術年會論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調度問題[A];1997年中國控制會議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調度問題研究[A];第25屆中國控制與決策會議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應調度:結構與算法研究[A];1992年中國控制與決策學術年會論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準備時間和交付期的單機E／T調度問題研究[A];1998年中國控制會議論文集[C];1998年

中國重要報紙全文數(shù)據庫 前2條

1 本報記者 賈科華;火電機組叫苦調度不合理[N];中國能源報;2012年

2 本報記者 高芳;牽住“牛鼻子” 巧解“推進難”[N];湖南經濟報;2008年

中國博士學位論文全文數(shù)據庫 前10條

1 郭鵬;具有分段惡化效應生產過程的智能優(yōu)化調度研究[D];西南交通大學;2014年

2 元野;基于圖著色模型的零擔物流調度優(yōu)化問題研究[D];哈爾濱工業(yè)大學;2015年

3 李雪松;模糊環(huán)境下若干單機批加工調度問題的模型及其算法研究[D];哈爾濱工業(yè)大學;2015年

4 湯雅連;關聯(lián)物流運輸調度問題研究[D];廣東工業(yè)大學;2015年

5 周理;高效可重構陣列計算：體系結構，設計方法與程序映射技術研究[D];國防科學技術大學;2014年

6 馮大光;一類批處理機調度的理論和方法研究[D];東北大學;2011年

7 孟盈;鋼鐵企業(yè)并行批生產決策與調度問題研究[D];東北大學;2011年

8 楊磊;內容網絡中內容調度技術研究[D];重慶大學;2015年

9 李亞志;流水制造單元調度智能優(yōu)化方法[D];東南大學;2015年

10 丁寧;若干調度問題的算法研究[D];大連理工大學;2016年

中國碩士學位論文全文數(shù)據庫 前10條

1 張亮;云計算環(huán)境下的資源調度技術的研究[D];江南大學;2015年

2 馮卓鵬;重載運輸卸車組織優(yōu)化研究[D];西南交通大學;2015年

3 崔雪源;基于遺傳模擬退火算法的航班著陸調度問題[D];華中師范大學;2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調度問題的研究[D];曲阜師范大學;2015年

5 張勇;帶拒絕和釋放時間的單機批調度問題[D];山東大學;2015年

6 吳凡;基于粒子群優(yōu)化算法的風電-火電機組組合調度研究[D];華北電力大學;2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調度問題研究[D];重慶理工大學;2015年

8 吉佳紅;基于細菌覓食算法的改進及應用研究[D];江蘇科技大學;2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學;2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調度研究[D];大連理工大學;2015年

，

本文編號：1126364