基于變鄰域搜索和布圖規(guī)劃的資源投資項目調(diào)度方法研究.pdf

1、在科技飛速發(fā)展的今天，項目調(diào)度問題越來越成為人們關(guān)注的焦點。資源投資項目調(diào)度問題(Resource Investment Project Scheduling Problems,RIPSPs)是項目調(diào)度問題的一個重要拓展，它解除了資源約束項目調(diào)度問題(Resource-Constrained Project Scheduling Problems,RCPSPs)中給定各種資源總量的限制，即問題變?yōu)榻o定一個項目，項目中包含多個活動，活動之

2、間有優(yōu)先約束關(guān)系，并且每個活動的執(zhí)行都需要一定的時間以及若干種資源。我們的任務(wù)是合理的安排活動之間的優(yōu)先約束關(guān)系，使得項目的完工時間最短，同時要滿足項目執(zhí)行的過程中需要的每種最大資源容量（稱之為可用資源容量）最小。本文針對單模式 RIPSPs，用不同的方法進行了研究，包括變鄰域搜索(Variable Neighborhood Search,VNS)，基于多智能體進化算法(Multi-agent Evolutionary Algorith

3、m,MAEA)的VNS以及布圖規(guī)劃中的基于移動模塊序列(Moving Block Sequence,MBS)的方法。主要研究內(nèi)容總結(jié)如下：
　　1.在基于 VNS的方法中，采用抖動操作及鄰域搜索算子，首先每個解由一個滿足優(yōu)先約束關(guān)系的活動列表和一個資源容量列表組成，然后從問題的一個可行解開始搜索，通過鄰域搜索算子找到局部最優(yōu)解，然后利用抖動操作跳出局部最優(yōu)解并繼續(xù)進行搜索，就這樣不停的擴大搜索空間，直到找到最優(yōu)解或者達到停止條件為

4、止。采用橋構(gòu)建數(shù)據(jù)集以及產(chǎn)生實例集J10、J14和J20驗證算法性能，實驗結(jié)果表明VNS比較適合解決小規(guī)模問題集。
　　2.在第一項基于VNS工作的基礎(chǔ)上，加入MAEA，采用選擇、交叉、變異、競爭等算子優(yōu)化算法性能，對于當前代中最好的智能體，以1/2的概率應用自學習算子或基于VNS的局部搜索算子進一步搜索解的空間，實驗表明所提出的算法性能良好。
　　3.提出將布圖規(guī)劃中MBS的表示方法和MAEA相結(jié)合求解RIPSPs。首先將