本文關(guān)鍵詞：基于GA與EDA的智能算法求解復(fù)雜車間調(diào)度問題

  更多相關(guān)文章： 分布估計(jì)算法 遺傳算法 零等待作業(yè)車間 可重入作業(yè)車間 最大完工時(shí)間

【摘要】：生產(chǎn)制造系統(tǒng)作為一類復(fù)雜的人造系統(tǒng),具有NP難、多局部最優(yōu)、不確定性、多目標(biāo)、多約束、非線性等特點(diǎn)。生產(chǎn)調(diào)度是制造系統(tǒng)的一個研究熱點(diǎn),也是理論研究中最為困難的問題之一。根據(jù)生產(chǎn)目標(biāo)和各種約束條件,為每個加工對象確定具體的加工路徑、時(shí)間、機(jī)器和操作等是調(diào)度的主要任務(wù)。鑒于復(fù)雜生產(chǎn)調(diào)度問題重要的應(yīng)用價(jià)值和理論意義,基于該問題的智能優(yōu)化算法研究已受到工業(yè)界和理論界的廣泛關(guān)注。遺傳算法(Genetic Algorithm,GA)作為一種經(jīng)典的群體智能優(yōu)化算法,已在各個領(lǐng)域得到廣泛應(yīng)用,而分布估計(jì)算法(Estimation of Distribution Algorithm,EDA)作為一種基于優(yōu)勢個體概率分布模型的新興智能優(yōu)化算法,近年已在多個工業(yè)領(lǐng)域得到了成功應(yīng)用。因此,本文對三類重要的車間調(diào)度問題進(jìn)行基于GA或EDA的求解算法研究。主要工作如下：(1)針對最大完工時(shí)間(makespan)指標(biāo)下的流水線車間調(diào)度問題,設(shè)計(jì)了一種帶有Insert鄰域局部搜索機(jī)制的遺傳算法,利用GA對問題解空間進(jìn)行搜索并發(fā)現(xiàn)優(yōu)質(zhì)解區(qū)域,同時(shí)采用局部搜索對優(yōu)質(zhì)解區(qū)域進(jìn)行較細(xì)致的搜索。通過在不同規(guī)模測試問題上的仿真實(shí)驗(yàn)驗(yàn)證了所提算法的有效性和魯棒性。(2)針對最大完工時(shí)間(makespan)指標(biāo)下的零等待作業(yè)車間調(diào)度問題,通過分析問題的結(jié)構(gòu)特性,設(shè)計(jì)了一種增強(qiáng)型的分布估計(jì)算法(Enhanced Estimation of Distribution Algorithm,EEDA)。該算法采用移位時(shí)間表方法對問題解進(jìn)行解碼,從而可直接提高基于工件排序編碼的解的質(zhì)量,同時(shí)利用2維概率矩陣作為EDA概率模型積累優(yōu)質(zhì)解信息并引導(dǎo)全局搜索,進(jìn)而加入了基于首次改進(jìn)跳出策略和Interchange鄰域的局部搜索。通過若干典型問題(benchmarks)進(jìn)行仿真實(shí)驗(yàn)并與其它有效算法進(jìn)行比較,驗(yàn)證了所提EEDA的有效性和魯棒性。(3)針對最大完工時(shí)間(makespan)指標(biāo)下帶序相關(guān)設(shè)置時(shí)間的可重作業(yè)車間調(diào)度問題,設(shè)計(jì)了一種基于貝葉斯統(tǒng)計(jì)推理的EDA算法(Bayesian Statistical Inference-Based EDA,BEDA)進(jìn)行求解。在該算法中,根據(jù)問題性質(zhì),采用活動化解碼來提高基于工序排列編碼的解的質(zhì)量,利用簡單貝葉斯網(wǎng)絡(luò)模型作為EDA概率模型描述問題變量間的關(guān)聯(lián)關(guān)系,同時(shí)學(xué)習(xí)和積累優(yōu)質(zhì)解信息,并引導(dǎo)算法搜索。通過仿真實(shí)驗(yàn)和算法比較驗(yàn)證了所提BEDA算法的有效性和魯棒性。
【關(guān)鍵詞】：分布估計(jì)算法 遺傳算法 零等待作業(yè)車間 可重入作業(yè)車間 最大完工時(shí)間
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP18;TB497
【目錄】：

• 摘要5-7
• Abstract7-12
• 第一章 緒論12-24
• 1.1 研究意義12
• 1.2 置換流水線調(diào)度問題研究12-13
• 1.2.1 置換流水線調(diào)度問題描述12-13
• 1.2.2 置換流水線調(diào)度問題研究概述13
• 1.3 零等待作業(yè)車間調(diào)度問題研究13-15
• 1.3.1 零等待作業(yè)車間調(diào)度問題描述13-14
• 1.3.2 零等待作業(yè)車間調(diào)度問題研究概述14-15
• 1.4 可重入作業(yè)車間調(diào)度問題研究15-17
• 1.4.1 可重入作業(yè)車間調(diào)度問題的數(shù)學(xué)模型描述15-16
• 1.4.2 可重入作業(yè)車間調(diào)度問題研究概述16-17
• 1.5 遺傳算法及其在智能調(diào)度領(lǐng)域的應(yīng)用17-19
• 1.5.1 遺傳算法17-18
• 1.5.2 遺傳算法在智能調(diào)度領(lǐng)域的應(yīng)用18-19
• 1.6 分布估計(jì)算法及其在智能調(diào)度領(lǐng)域的應(yīng)用19-21
• 1.6.1 分布估計(jì)算法19-21
• 1.6.2 分布估計(jì)算法在智能調(diào)度領(lǐng)域的應(yīng)用21
• 1.7 主要研究工作21-24
• 第二章 求解流水線調(diào)度問題的改進(jìn)遺傳算法24-30
• 2.1 引言24
• 2.2 以最小化最大完工時(shí)間為目標(biāo)的置換流水線調(diào)度問題描述24-25
• 2.3 改進(jìn)遺傳算法25-27
• 2.3.1 解的表達(dá)25
• 2.3.2 種群初始化25
• 2.3.3 基于Insert鄰域的局部搜索25-26
• 2.3.4 選擇操作26
• 2.3.5 交叉操作26
• 2.3.6 變異操作26-27
• 2.3.7 改進(jìn)遺傳算法步驟27
• 2.4 仿真實(shí)驗(yàn)與分析27-29
• 2.4.1 實(shí)驗(yàn)設(shè)置27-28
• 2.4.2 性能比較28-29
• 2.4.3 仿真結(jié)果和對比29
• 2.5 小結(jié)29-30
• 第三章 求解零等待車間調(diào)度問題的增強(qiáng)型EDA算法30-42
• 3.1 引言30-31
• 3.2 零等待作業(yè)車間調(diào)度問題描述31-35
• 3.2.1 問題模型31-32
• 3.2.2 時(shí)間表確定問題32-35
• 3.3 增強(qiáng)型分布估計(jì)算法35-39
• 3.3.1 解的表達(dá)35
• 3.3.2 種群初始化35
• 3.3.3 新種群的生成35-36
• 3.3.4 基于Insert的變異策略36-37
• 3.3.5 基于首次改進(jìn)原則的鄰域搜索策略37
• 3.3.6 增強(qiáng)型分布估計(jì)算法步驟37-39
• 3.4 仿真實(shí)驗(yàn)與分析39-40
• 3.4.1 實(shí)驗(yàn)設(shè)置39
• 3.4.2 性能比較39-40
• 3.4.3 仿真結(jié)果和對比40
• 3.5 小結(jié)40-42
• 第四章 求解帶序設(shè)置時(shí)間的可重入車間調(diào)度問題的貝葉斯分布估計(jì)算法42-52
• 4.1 引言42-43
• 4.2 帶序設(shè)置時(shí)間的可重入作業(yè)車間調(diào)度問題描述43-45
• 4.3 基于貝葉斯網(wǎng)絡(luò)的分布式估計(jì)算法45-50
• 4.3.1 解的表達(dá)45
• 4.3.2 種群初始化策略45
• 4.3.3 解碼方案45
• 4.3.4 概率模型及其更新策略45-48
• 4.3.4.1 概率模型45-46
• 4.3.4.2 概率模型更新策略46-48
• 4.3.5 新種群的生成48-49
• 4.3.6 基于Insert的鄰域結(jié)構(gòu)49
• 4.3.7 基于貝葉斯網(wǎng)絡(luò)的分布式估計(jì)算法步驟49-50
• 4.4 仿真實(shí)驗(yàn)與分析50-51
• 4.4.1 實(shí)驗(yàn)設(shè)置50
• 4.4.2 性能比較50
• 4.4.3 仿真結(jié)果和對比50-51
• 4.5 小結(jié)51-52
• 第五章 結(jié)論與展望52-54
• 5.1 論文總結(jié)52-53
• 5.2 研究展望53-54
• 致謝54-56
• 參考文獻(xiàn)56-62
• 附錄A (攻讀碩士學(xué)位期間的科研成果)62

【相似文獻(xiàn)】

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

1 潘全科;趙保華;屈玉貴;畢于慧;;一類解決無等待流水車間調(diào)度問題的蟻群算法[J];計(jì)算機(jī)集成制造系統(tǒng);2007年09期

2 何利;劉永賢;劉笑天;;粒子群優(yōu)化算法求解車間調(diào)度問題[J];機(jī)械與電子;2007年08期

3 王秋芬;楊澤平;梁道雷;;一種改進(jìn)的車間調(diào)度問題算法[J];科學(xué)技術(shù)與工程;2013年11期

4 蘇子林;;車間調(diào)度問題及其進(jìn)化算法分析[J];機(jī)械工程學(xué)報(bào);2008年08期

5 徐建有;董乃群;顧樹生;;帶有順序相關(guān)調(diào)整時(shí)間的多目標(biāo)流水車間調(diào)度問題[J];計(jì)算機(jī)集成制造系統(tǒng);2013年12期

6 康寧,王鳳儒,劉丕娥,常會友;有交貨期的單件車間調(diào)度問題的逆序算法[J];系統(tǒng)工程理論與實(shí)踐;1999年12期

7 馬邦雄;葉春明;;利用貓群算法求解流水車間調(diào)度問題[J];現(xiàn)代制造工程;2014年06期

8 曲媛;楊曉偉;;關(guān)于流水車間調(diào)度問題的綜述[J];中小企業(yè)科技;2007年08期

9 王柏琳;李鐵克;;等待時(shí)間受限的流水車間調(diào)度問題的若干性質(zhì)[J];系統(tǒng)工程理論與實(shí)踐;2012年06期

10 邵揚(yáng);王曉娟;;類電磁機(jī)制算法求解模糊流水車間調(diào)度問題[J];武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版);2013年02期

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

1 鄒逢興;曾令李;高政;劉烽;;一種求解混合流水車間調(diào)度問題的分布式方法[A];2009中國控制與決策會議論文集（2）[C];2009年

2 朱婧;;求解車間調(diào)度問題的改進(jìn)模擬退火算法[A];第五屆（2010）中國管理學(xué)年會——商務(wù)智能分會場論文集[C];2010年

3 洪宗友;龐哈利;;No-wait流水車間調(diào)度問題的一種啟發(fā)式算法[A];2007中國控制與決策學(xué)術(shù)年會論文集[C];2007年

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

1 陶翼飛;面向分組加工的混合流水車間優(yōu)化調(diào)度問題研究[D];昆明理工大學(xué);2013年

2 何利;即時(shí)定制生產(chǎn)模式及其車間調(diào)度問題的研究[D];東北大學(xué);2008年

3 黃英杰;基于目標(biāo)級聯(lián)法和智能優(yōu)化算法的車間調(diào)度問題研究[D];華南理工大學(xué);2012年

4 劉延風(fēng);置換流水車間調(diào)度問題的幾種智能算法[D];西安電子科技大學(xué);2012年

5 常桂娟;基于微粒群算法的車間調(diào)度問題研究[D];青島大學(xué);2008年

6 崔U，

本文編號：1056700