本文關(guān)鍵詞：有模具限制的并行機臺調(diào)度問題研究

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

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

• 摘要4-6
• Abstract6-10
• 第一章 緒論10-20
• 1.1 研究背景及意義10-12
• 1.2 國內(nèi)外研究現(xiàn)狀12-16
• 1.2.1 國外研究現(xiàn)狀12-14
• 1.2.2 國內(nèi)研究現(xiàn)狀14-16
• 1.3 主要的研究內(nèi)容及結(jié)構(gòu)安排16-20
• 1.3.1 主要研究內(nèi)容16-18
• 1.3.2 本文的結(jié)構(gòu)安排18-20
• 第二章 數(shù)學(xué)模型與啟發(fā)式算法20-42
• 2.1 問題的背景與描述20-22
• 2.2 混合整數(shù)規(guī)劃模型的建立22-27
• 2.2.1 符號及變量的定義22-23
• 2.2.2 數(shù)學(xué)模型的建立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 本章小結(jié)40-42
• 第三章 萬用啟發(fā)式演算法的設(shè)計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 本章小結(jié)58-60
• 第四章 實驗分析及應(yīng)用實例60-74
• 4.1 實驗的目的及應(yīng)用背景60-61
• 4.2 實驗的環(huán)境及參數(shù)設(shè)置61-62
• 4.3 實驗的結(jié)果及對比分析62-72
• 4.4 本章小結(jié)72-74
• 第五章 結(jié)論與展望74-76
• 5.1 全文結(jié)論74-75
• 5.2 未來展望75-76
• 參考文獻76-82
• 作者簡介82-84
• 攻讀學(xué)位期間主要從事的科研工作84-86
• 致謝86

【相似文獻】

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

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

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

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

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

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

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

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

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

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

10 董平;機器調(diào)度問題及求解方法[J];物流技術(shù)與應(yīng)用;1997年01期

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

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

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

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

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

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

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

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

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

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國控制與決策學(xué)術(shù)年會論文集[C];1992年

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

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

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

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

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

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

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

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

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

5 周理;高效可重構(gòu)陣列計算：體系結(jié)構(gòu)，設(shè)計方法與程序映射技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2014年

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

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

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學(xué);2015年

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

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學(xué);2016年

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1126364