本文關(guān)鍵詞：求解RCPSP問(wèn)題的迭代局部搜索算法研究

  更多相關(guān)文章： 迭代局部搜索 資源約束項(xiàng)目調(diào)度問(wèn)題 擾動(dòng) 關(guān)鍵鏈 雙對(duì)齊

【摘要】：資源約束項(xiàng)目調(diào)度問(wèn)題(Resource-constrained Project Scheduling Problem, RCPSP)的主要任務(wù)是為調(diào)度項(xiàng)目的活動(dòng)安排時(shí)間和資源,合理使用資源實(shí)現(xiàn)既定目標(biāo)的最優(yōu)化。近年來(lái)由于企業(yè)信息化的快速發(fā)展和項(xiàng)目管理的需要,該問(wèn)題被越來(lái)越廣泛地研究和應(yīng)用,對(duì)該問(wèn)題的進(jìn)一步研究也具有很高的研究?jī)r(jià)值和應(yīng)用前景。本文提出了一種應(yīng)用于資源約束項(xiàng)目調(diào)度問(wèn)題的迭代局部搜索算法(Iterated Local Search,ILS)。迭代局部搜索算法是一類簡(jiǎn)單而高效的元啟發(fā)式算法,成功地應(yīng)用于諸多組合優(yōu)化問(wèn)題。本文將ILS算法應(yīng)用于RCPSP問(wèn)題,通過(guò)對(duì)算法的進(jìn)一步改進(jìn)和優(yōu)化,使其更適用于RCPSP問(wèn)題。首先研究產(chǎn)生初始解的方法。本文通過(guò)實(shí)驗(yàn)比較了多種求解較優(yōu)的啟發(fā)式算法,最終選擇最早開(kāi)始時(shí)間(Earliest Start Time,EST)優(yōu)先規(guī)則配合串行調(diào)度生成方案(Serial Schedule Generation Scheme,SSGS)的方式生成初始解。同時(shí)為了進(jìn)一步優(yōu)化局部搜索過(guò)程使其更適用于RCPSP問(wèn)題,研究了插入和交換兩種局部搜索方法的求解性能,設(shè)計(jì)了使用迭代交換的方式優(yōu)化當(dāng)前解的局部搜索過(guò)程。為克服局部搜索過(guò)程容易陷入局部最優(yōu)的缺點(diǎn),針對(duì)RCPSP問(wèn)題,本文提出了一種擾動(dòng)策略,通過(guò)動(dòng)態(tài)擾動(dòng)多個(gè)任務(wù)的方式防止過(guò)早陷入局部最優(yōu)。為進(jìn)一步提高搜索效率,本文分別研究了在局部搜索過(guò)程中使用關(guān)鍵鏈和關(guān)鍵路徑信息的方法。通過(guò)以上改進(jìn)策略,最終完成了應(yīng)用于RCPSP問(wèn)題的迭代局部搜索算法。本文的優(yōu)化目標(biāo)是最小化項(xiàng)目的完工時(shí)間。在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明提出的算法是有效的。
【關(guān)鍵詞】：迭代局部搜索 資源約束項(xiàng)目調(diào)度問(wèn)題 擾動(dòng) 關(guān)鍵鏈 雙對(duì)齊
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6
【目錄】：

• 致謝5-6
• 摘要6-7
• ABSTRACT7-10
• 1 引言10-17
• 1.1 研究背景與意義10-12
• 1.2 國(guó)內(nèi)外研究現(xiàn)狀12-14
• 1.3 迭代局部搜索算法簡(jiǎn)介14-15
• 1.4 論文主要內(nèi)容15-16
• 1.5 論文基本結(jié)構(gòu)16
• 1.6 本章小結(jié)16-17
• 2 經(jīng)典資源約束項(xiàng)目調(diào)度問(wèn)題及求解算法17-27
• 2.1 不考慮資源約束的項(xiàng)目調(diào)度17-18
• 2.2 約束描述18-20
• 2.2.1 邏輯約束19
• 2.2.2 資源約束19-20
• 2.3 問(wèn)題目標(biāo)20-21
• 2.4 模型描述21-23
• 2.5 算法研究現(xiàn)狀23-26
• 2.5.1 精確算法23-24
• 2.5.2 啟發(fā)式算法24-26
• 2.6 本章小結(jié)26-27
• 3 應(yīng)用于RCPSP問(wèn)題的ILS算法27-40
• 3.1 基本定義27-29
• 3.2 算法思想29
• 3.3 算法框架29-30
• 3.4 算法描述30-38
• 3.4.1 產(chǎn)生初始解和解的標(biāo)準(zhǔn)化31-32
• 3.4.2 關(guān)鍵鏈方法32-34
• 3.4.3 局部搜索過(guò)程34
• 3.4.4 擾動(dòng)策略34-35
• 3.4.5 交換過(guò)程35-36
• 3.4.6 提出的ILS算法36-38
• 3.5 算法的可行性分析38-39
• 3.6 本章小結(jié)39-40
• 4 參數(shù)評(píng)估和實(shí)驗(yàn)結(jié)果分析40-51
• 4.1 實(shí)驗(yàn)數(shù)據(jù)集及環(huán)境40-42
• 4.2 優(yōu)化策略42-47
• 4.2.1 擾動(dòng)方式對(duì)比42-43
• 4.2.2 驗(yàn)證精英解池43-44
• 4.2.3 驗(yàn)證局部搜索過(guò)程的交換方式44-45
• 4.2.4 關(guān)鍵路徑和關(guān)鍵鏈對(duì)比45-46
• 4.2.5 驗(yàn)證算法擾動(dòng)過(guò)程的交換方式46-47
• 4.3 參數(shù)評(píng)估47-49
• 4.3.1 擾動(dòng)強(qiáng)度評(píng)估47
• 4.3.2 參數(shù)max_cnt的確定47-48
• 4.3.3 迭代終止條件的選擇48-49
• 4.4 實(shí)驗(yàn)結(jié)果49
• 4.5 本章小結(jié)49-51
• 5 總結(jié)與展望51-53
• 5.1 論文總結(jié)51-52
• 5.2 論文展望52-53
• 參考文獻(xiàn)53-58
• 作者簡(jiǎn)歷及攻讀碩士學(xué)位期間取得的研究成果58-60
• 學(xué)位論文數(shù)據(jù)集60

【相似文獻(xiàn)】

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

1 張雁;黃永宣;魏明海;;一種求解最大團(tuán)問(wèn)題的自適應(yīng)過(guò)濾局部搜索算法[J];信息與控制;2011年04期

2 肖進(jìn)杰,朱大銘,馬紹漢,潘銳;多服務(wù)中心設(shè)置問(wèn)題局部搜索算法的分析與實(shí)驗(yàn)[J];計(jì)算機(jī)工程;2005年12期

3 謝嘯虎;黃樟燦;焉炳艷;;多目標(biāo)遺傳局部搜索算法的研究進(jìn)展[J];武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版);2006年12期

4 潘銳;朱大銘;董林光;董穎;;求解k中間點(diǎn)問(wèn)題的新局部搜索算法[J];計(jì)算機(jī)工程與應(yīng)用;2008年04期

5 詹青青;;啟發(fā)式局部搜索算法在電路劃分中的應(yīng)用[J];福建電腦;2010年04期

6 韋煒;藤村茂;席裕庚;;求解旅行錦標(biāo)賽問(wèn)題的改進(jìn)混合局部搜索算法[J];計(jì)算機(jī)仿真;2012年10期

7 吳貴芳,徐科,徐金梧;邊界局部搜索算法與應(yīng)用[J];計(jì)算機(jī)應(yīng)用;2005年02期

8 肖進(jìn)杰;謝青松;牛翠霞;;設(shè)備定位問(wèn)題局部搜索算法的實(shí)驗(yàn)[J];計(jì)算機(jī)工程與應(yīng)用;2010年02期

9 陳萍;黃厚寬;董興業(yè);;基于多鄰域的車輛路徑優(yōu)化迭代局部搜索算法[J];北京交通大學(xué)學(xué)報(bào);2009年02期

10 王健;趙娜;劉超;孫志禮;;粒子群及局部搜索算法在串并聯(lián)系統(tǒng)結(jié)構(gòu)優(yōu)化中的應(yīng)用[J];機(jī)械與電子;2014年01期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

1 劉心報(bào);葉強(qiáng);;基于模塊設(shè)計(jì)的蟻群算法研究綜述[A];'2008系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2008年

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

1 趙軒;求解RCPSP問(wèn)題的迭代局部搜索算法研究[D];北京交通大學(xué);2016年

2 咸愛(ài)勇;合取范式最大不全滿足與最大可滿足問(wèn)題的局部搜索算法研究[D];山東大學(xué);2012年

3 高超;隨機(jī)局部搜索算法及其應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2015年

4 殷茜;基于局部搜索的最小可滿足問(wèn)題求解算法研究[D];東北師范大學(xué);2015年

5 溫真真;需求可拆分車輛路徑問(wèn)題的迭代局部搜索算法研究[D];北京交通大學(xué);2015年

6 顏遠(yuǎn)輝;賦權(quán)MAX-SAT問(wèn)題的動(dòng)態(tài)凸化方法[D];福州大學(xué);2011年

，

本文編號(hào)：1078432