求解RCPSP問題的迭代局部搜索算法研究.pdf

1、資源約束項目調(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 Searc

2、h, 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 S

3、cheme，SSGS)的方式生成初始解。同時為了進一步優(yōu)化局部搜索過程使其更適用于RCPSP問題，研究了插入和交換兩種局部搜索方法的求解性能，設(shè)計了使用迭代交換的方式優(yōu)化當(dāng)前解的局部搜索過程。為克服局部搜索過程容易陷入局部最優(yōu)的缺點，針對RCPSP問題，本文提出了一種擾動策略，通過動態(tài)擾動多個任務(wù)的方式防止過早陷入局部最優(yōu)。為進一步提高搜索效率，本文分別研究了在局部搜索過程中使用關(guān)鍵鏈和關(guān)鍵路徑信息的方法。通過以上改進策略，最終完成了應(yīng)