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

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

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

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

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