求解動態(tài)資源投資項目調(diào)度問題的多目標進化算法.pdf

1、在我們的日常生活中，調(diào)度問題無處不在，比如十字路口的車輛調(diào)度，工廠中的生產(chǎn)調(diào)度，操作系統(tǒng)中的線程調(diào)度等等。項目調(diào)度主要是從時間和資源上進行考慮進而合理地安排項目活動的執(zhí)行。傳統(tǒng)項目調(diào)度問題主要研究確定環(huán)境下的調(diào)度問題，而在實際的項目調(diào)度過程中往往存在各種各樣的不確定性，例如由于環(huán)境的變化某種資源不能按時到達，導(dǎo)致某個活動的執(zhí)行時間變長；或者由于某些突發(fā)事件，項目中某些活動的優(yōu)先關(guān)系需要進行調(diào)整以及另外一些還沒有顯示出來的不確定性，所以研

2、究不確定環(huán)境下的調(diào)度問題受到越來越多的關(guān)注。
　　本文先對已有的項目調(diào)度問題進行了總結(jié)和歸納，接著在已有問題的層次和范圍方面進行擴展。研究模型從單一目標變?yōu)槎嗄繕四Ｐ?，研究環(huán)境從確定環(huán)境轉(zhuǎn)變?yōu)椴淮_定環(huán)境。接下來我們介紹本文研究的關(guān)于資源投資項目調(diào)度問題(RIPSP)的模型以及相應(yīng)解決算法。首先，我們研究了靜態(tài)環(huán)境下的資源投資項目調(diào)度問題，利用差分算法和局部搜索算子進行優(yōu)化處理；接著研究了動態(tài)環(huán)境下的多目標資源投資項目調(diào)度優(yōu)化問題，

3、其中動態(tài)環(huán)境是基于情景模式采樣產(chǎn)生的；最后，鑒于情景模式采樣需要大量的時間和資源，我們采用魯棒代理模型研究動態(tài)環(huán)境下的資源投資項目調(diào)度問題的解魯棒性。本論文主要工作可總結(jié)如下：
　　(1)將差分算法和局部搜索算子相結(jié)合解決靜態(tài)資源投資項目調(diào)度問題，我們稱此算法為DELS-RIPSP，這里是一個基于延遲懲罰的最小化項目花費問題。差分算法和局部搜索算子相結(jié)合能夠有效提升現(xiàn)有個體的性能從而提高整個種群的質(zhì)量。在實驗中，我們測試了450個

4、基準問題，目的在于評估差分算法和局部搜索算子相結(jié)合能否有效地解決資源投資項目調(diào)度問題。最后，實驗結(jié)果證明差分算法和局部搜索算子相結(jié)合能夠快速地找到資源投資項目調(diào)度問題的最優(yōu)解，并且在解決大型項目的資源投資項目調(diào)度問題方面比較有潛力。
　　(2)研究基于工期不確定性多目標的動態(tài)資源投資項目調(diào)度問題(DP-RIPSPs)，提出了一個更吻合現(xiàn)實調(diào)度過程的多目標研究模型，基于此多目標模型研究不確定環(huán)境下的資源投資項目調(diào)度方案魯棒性的問題。

5、其中，不確定性指項目執(zhí)行過程中的活動工期是不確定的，并且不確定性是通過情景模式采樣來模擬的。我們采用非支配排序遺傳算法(NSGA-II)和改進的非支配排序遺傳算法(NSGAM-II)分別解決基于不確定性的多目標資源投資項目調(diào)度優(yōu)化問題。改進的非支配排序遺傳算法受益于局部搜索算子能夠快速找到最優(yōu)解。我們對1152個基準問題分別進行了測試，結(jié)果表明NSGAM-II比NSGA-II能夠更快速地找到方案魯棒性解。
　　(3)鑒于第二部分采