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

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

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

• 致謝5-6
• 摘要6-7
• ABSTRACT7-10
• 1 引言10-17
• 1.1 研究背景與意義10-12
• 1.2 國內(nèi)外研究現(xiàn)狀12-14
• 1.3 迭代局部搜索算法簡介14-15
• 1.4 論文主要內(nèi)容15-16
• 1.5 論文基本結(jié)構(gòu)16
• 1.6 本章小結(jié)16-17
• 2 經(jīng)典資源約束項目調(diào)度問題及求解算法17-27
• 2.1 不考慮資源約束的項目調(diào)度17-18
• 2.2 約束描述18-20
• 2.2.1 邏輯約束19
• 2.2.2 資源約束19-20
• 2.3 問題目標(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問題的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 局部搜索過程34
• 3.4.4 擾動策略34-35
• 3.4.5 交換過程35-36
• 3.4.6 提出的ILS算法36-38
• 3.5 算法的可行性分析38-39
• 3.6 本章小結(jié)39-40
• 4 參數(shù)評估和實驗結(jié)果分析40-51
• 4.1 實驗數(shù)據(jù)集及環(huán)境40-42
• 4.2 優(yōu)化策略42-47
• 4.2.1 擾動方式對比42-43
• 4.2.2 驗證精英解池43-44
• 4.2.3 驗證局部搜索過程的交換方式44-45
• 4.2.4 關(guān)鍵路徑和關(guān)鍵鏈對比45-46
• 4.2.5 驗證算法擾動過程的交換方式46-47
• 4.3 參數(shù)評估47-49
• 4.3.1 擾動強度評估47
• 4.3.2 參數(shù)max_cnt的確定47-48
• 4.3.3 迭代終止條件的選擇48-49
• 4.4 實驗結(jié)果49
• 4.5 本章小結(jié)49-51
• 5 總結(jié)與展望51-53
• 5.1 論文總結(jié)51-52
• 5.2 論文展望52-53
• 參考文獻53-58
• 作者簡歷及攻讀碩士學(xué)位期間取得的研究成果58-60
• 學(xué)位論文數(shù)據(jù)集60

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1078432