本文關鍵詞：一個特殊資源約束項目調(diào)度問題模型及其優(yōu)化算法研究

  更多相關文章： 資源約束項目調(diào)度問題 工位約束 串行進度生成機制 迭代局部搜索 最大最小螞蟻系統(tǒng)

【摘要】：項目調(diào)度問題在企業(yè)生產(chǎn)中有著很重要的作用,與生產(chǎn)效率、成本密切相關。由于企業(yè)生產(chǎn)過程的多樣性,經(jīng)典資源約束項目調(diào)度問題(RCPSP)在實際生產(chǎn)中并不適用,所以,本文基于某企業(yè)的實際需求,在RCPSP基礎上加入了工位、工件等新的概念,增加了工位對可更新資源、工件加工的約束,設定最小化總流程時間和最小化總偏差時間為求解目標,提出了一個新的項目調(diào)度問題模型——特殊資源約束項目調(diào)度問題(SRCPSP),用以解決實際調(diào)度問題。由于RCPSP是NP-hard問題,而SRCPSP約束更為復雜,所以,只能使用啟發(fā)式算法進行求解。本文首先使用基于串行進度生成機制和優(yōu)先規(guī)則的啟發(fā)式算法對SRCPSP進行求解,提出了三大類規(guī)則分別用于選擇工位、選擇資源和選擇工序,實驗表明該算法可以快速生成一個初始可行解。然后,在此基礎上,對初始解進行優(yōu)化算法研究。首先,本文實驗了使用迭代局部搜索的方法,研究了使用迭代局部搜索時解的表示方式、鄰域結(jié)構、擾動策略等,然而研究表明,由于工件在工位間移動的巨大時間代價,迭代局部搜索并不適用于帶工位約束的項目調(diào)度問題。之后,考慮到工序的調(diào)度主要是合適的工位和資源,所以本文實驗了為工序隨機選擇工位和資源,結(jié)果表明,隨機選擇工位可以產(chǎn)生更好的結(jié)果。根據(jù)此結(jié)果,本文將蟻群優(yōu)化算法——最大最小螞蟻系統(tǒng)(MMAS)——應用到工位選擇上,并用實驗確定了蟻群算法中各項參數(shù)。實驗表明,使用最大最小螞蟻系統(tǒng)優(yōu)化工位選擇過程的方法是切實有效的,并且在生成相同數(shù)量解的情況下,相較于隨機選擇是穩(wěn)定較優(yōu)的。因此,對于本文提出的SRCPSP模型,設計的基于MMAS的優(yōu)化算法具有很好的求解效果,將MMAS應用到工位選擇上是合理有效的。
【關鍵詞】：資源約束項目調(diào)度問題 工位約束 串行進度生成機制 迭代局部搜索 最大最小螞蟻系統(tǒng)
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-19
• 1.1 研究背景及意義11-15
• 1.1.1 基本概念及約束11-13
• 1.1.2 RCPSP模型13
• 1.1.3 求解算法13-15
• 1.1.4 RCPSP局限性及本文研究意義15
• 1.2 國內(nèi)外研究現(xiàn)狀15-18
• 1.2.1 RCPSP模型擴展研究現(xiàn)狀15-17
• 1.2.2 算法研究現(xiàn)狀17-18
• 1.3 論文主要內(nèi)容和組織結(jié)構18
• 1.4 本章小結(jié)18-19
• 2 特殊資源約束項目調(diào)度問題模型19-28
• 2.1 環(huán)境數(shù)據(jù)19-21
• 2.1.1 工件20
• 2.1.2 工位20
• 2.1.3 資源20-21
• 2.1.4 工序21
• 2.2 約束關系21-24
• 2.2.1 資源約束22-23
• 2.2.2 工序約束23-24
• 2.3 問題目標24
• 2.4 模型舉例24-27
• 2.5 本章小結(jié)27-28
• 3 基于優(yōu)先規(guī)則的SSGS啟發(fā)式算法28-36
• 3.1 基本概念及定義28-29
• 3.2 算法總體流程29-30
• 3.3 優(yōu)先規(guī)則30-33
• 3.3.1 工位選擇規(guī)則30-31
• 3.3.2 資源選擇規(guī)則31
• 3.3.3 工序選擇規(guī)則31-32
• 3.3.4 解鎖規(guī)則32-33
• 3.4 輸入及輸出數(shù)據(jù)格式33
• 3.4.1 輸入數(shù)據(jù)33
• 3.4.2 輸出數(shù)據(jù)33
• 3.5 本章小結(jié)33-36
• 4 基于迭代局部搜索的優(yōu)化算法36-45
• 4.1 迭代局部搜索算法36-37
• 4.2 SRCPSP問題的迭代局部搜索優(yōu)化算法設計37-42
• 4.2.1 解的表示37-38
• 4.2.2 鄰域結(jié)構38-39
• 4.2.3 擾動策略39-40
• 4.2.4 算法總流程設計40-42
• 4.3 實驗與結(jié)果分析42-44
• 4.4 本章小結(jié)44-45
• 5 基于蟻群算法的優(yōu)化算法45-61
• 5.1 隨機抽樣算法45-49
• 5.1.1 工位隨機選擇算法47
• 5.1.2 資源隨機選擇算法47
• 5.1.3 實驗驗證及分析47-49
• 5.2 蟻群算法49-56
• 5.2.1 蟻群優(yōu)化算法49-50
• 5.2.2 基于MMAS的優(yōu)化算法設計與實現(xiàn)50-52
• 5.2.3 基于MMAS的優(yōu)化算法參數(shù)選擇52-56
• 5.3 實驗結(jié)果與分析56-60
• 5.3.1 測試用例描述56-57
• 5.3.2 性能和可行性測試57-59
• 5.3.3 MMAS優(yōu)化算法與隨機算法對比59-60
• 5.4 本章小結(jié)60-61
• 6 總結(jié)與展望61-63
• 6.1 本文總結(jié)61-62
• 6.2 展望及今后的工作62-63
• 參考文獻63-67
• 作者簡歷及攻讀碩士學位期間取得的研究成果67-69
• 學位論文數(shù)據(jù)集69

【相似文獻】

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

1 宋紅星;曹文彬;;基于雙種群蟻群算法的多目標資源受限項目調(diào)度問題研究[J];信息系統(tǒng)工程;2010年04期

2 程序;吳澄;;一種復雜項目調(diào)度問題的混合智能算法[J];計算機集成制造系統(tǒng);2006年04期

3 徐進;費少梅;張樹有;施岳定;;自適應粒子群求解資源動態(tài)分配項目調(diào)度問題[J];計算機集成制造系統(tǒng);2011年08期

4 雒興剛;汪定偉;唐加福;;任務可拆分項目調(diào)度問題[J];東北大學學報;2006年09期

5 宗硯;劉瓊;張超勇;朱海平;;考慮資源傳遞時間的多項目調(diào)度問題[J];計算機集成制造系統(tǒng);2011年09期

6 孫曉雅;林焰;;任務可定點拆分的資源受限項目調(diào)度問題研究[J];微電子學與計算機;2012年07期

7 張維存;康凱;;蟻群-粒子群算法求解多模式資源受限項目調(diào)度問題[J];計算機工程與應用;2007年34期

8 劉敏;代成琴;王宇航;;資源受限的項目調(diào)度問題的求解算法[J];自動化技術與應用;2008年06期

9 盧睿;李林瑛;;一種求解反應式項目調(diào)度問題的啟發(fā)式方法[J];系統(tǒng)仿真學報;2011年02期

10 孫曉雅;林焰;;人工蜂群算法求解任務可拆分項目調(diào)度問題[J];微電子學與計算機;2011年11期

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

1 丁雪楓;尤建新;;多模式資源受限項目調(diào)度問題的混合優(yōu)化算法研究[A];第十四屆中國管理科學學術年會論文集(上冊)[C];2012年

2 劉艷秋;張穎;汪定偉;王福利;;基于GA的RCPSP可靠性優(yōu)化方法研究[A];2001年中國智能自動化會議論文集（下冊）[C];2001年

3 周楷;何正文;;周期性支付的多模式Max-npv項目調(diào)度問題研究[A];中國企業(yè)運籌學學術交流大會論文集[C];2008年

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

1 王宏;求解資源受限項目調(diào)度問題算法的研究[D];天津大學;2005年

2 鄧林義;資源受限的項目調(diào)度問題及其應用研究[D];大連理工大學;2008年

3 陳衛(wèi)明;動態(tài)環(huán)境下產(chǎn)品開發(fā)項目調(diào)度問題及其求解研究[D];華中科技大學;2011年

4 吳兵;柔性資源受限的多模式項目調(diào)度問題研究[D];武漢理工大學;2008年

5 彭武良;面向產(chǎn)品開發(fā)的項目調(diào)度問題及項目管理系統(tǒng)研究[D];東北大學;2008年

6 李詩嫻;基于凈現(xiàn)值的資源受限型項目調(diào)度問題研究[D];天津大學;2012年

7 賈艷;資源受限項目調(diào)度問題的仿真優(yōu)化方法及其應用研究[D];華中科技大學;2012年

8 應瑛;不確定資源約束下項目調(diào)度問題研究[D];浙江大學;2010年

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

1 李遠見;幾種改進的智能算法及其應用[D];安徽師范大學;2015年

2 段向陽;基于遺傳算法的資源約束項目調(diào)度問題優(yōu)化及應用研究[D];湖南工業(yè)大學;2015年

3 栗明威;一個特殊資源約束項目調(diào)度問題模型及其優(yōu)化算法研究[D];北京交通大學;2016年

4 張冠群;基于蟻群算法的多模式資源受限項目調(diào)度問題研究[D];湖南大學;2009年

5 傅奧;多目標資源受限項目調(diào)度問題蟻群算法研究[D];浙江大學;2008年

6 蒲娟;多目標模糊資源受限項目調(diào)度問題研究[D];鄭州大學;2012年

7 薄銀利;基于模塊化外包的項目調(diào)度問題研究[D];蘭州大學;2011年

8 劉志霞;資源受限項目調(diào)度問題及其任務擾動的干擾管理研究[D];沈陽工業(yè)大學;2011年

9 陳俊波;考慮施工設備租賃的項目調(diào)度問題研究[D];華中科技大學;2009年

10 劉雅婷;人力資源受限項目調(diào)度問題研究[D];華中科技大學;2007年

，

本文編號：759811