王 南，馬 永，陳笑蓉

(1.廣州市地下鐵道總公司，廣東 廣州 510180;2.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025)

多模式資源受限多項(xiàng)目調(diào)度問(wèn)題(Multi Mode Resource－Constrained Multi Project Scheduling Problem，MMRCMPSP)是基于技術(shù)、資源條件和項(xiàng)目間等約束，采用目標(biāo)優(yōu)化策略，優(yōu)化項(xiàng)目計(jì)劃調(diào)度，并在企業(yè)和軟件工程等領(lǐng)域具有廣泛的應(yīng)用。MMRCMPSP為NP－h(huán)ard 問(wèn)題，精確算法由于受任務(wù)數(shù)量、時(shí)間限制，常常應(yīng)用有限，出現(xiàn)了很多啟發(fā)算法和元啟發(fā)優(yōu)化算法。

傳統(tǒng)多項(xiàng)目管理中，基于Gold 博士的約束理論［1］，開(kāi)啟項(xiàng)目調(diào)度研究新方法。Leach［2］對(duì)于優(yōu)先權(quán)項(xiàng)目進(jìn)行管理，重點(diǎn)是找出多項(xiàng)目共享關(guān)鍵資源約束。劉士新［3］建立多目標(biāo)首先資源項(xiàng)目?jī)?yōu)化調(diào)度模式，采用基于關(guān)鍵鏈項(xiàng)目調(diào)度的優(yōu)先規(guī)則啟發(fā)式算法。Cai Z［4］等提出了混合遺傳算法求解方法。賈艷［5］針對(duì)多模式單項(xiàng)目提出了粒子群基因表達(dá)式編程混合算法對(duì)調(diào)度規(guī)則求解。彭京［6］等提出了基于多層染色體基因表達(dá)式編程的遺傳進(jìn)化算法。葉春明［7］等將建立混沌粒子群算法尋找關(guān)鍵鏈項(xiàng)目進(jìn)度調(diào)度。王軍強(qiáng)［8］等通過(guò)建立蟻群算法、資源調(diào)度模型，對(duì)多項(xiàng)目的時(shí)序約束、資源約束多目標(biāo)調(diào)度的分解求解方法。張凱［9］基于拓?fù)渑判虻泥徲蛩阉魉惴Ｐ湍軌蜥槍?duì)單項(xiàng)目實(shí)例找到較優(yōu)解。而戴月明［10］等則建立協(xié)同震蕩搜索混沌粒子群對(duì)首先項(xiàng)目調(diào)度研究。王偉鑫［11］等通過(guò)建立云遺傳算法對(duì)全局搜索、快速收斂有比較好的效果。對(duì)于多模式調(diào)度通常采用優(yōu)先權(quán)方法，調(diào)度的結(jié)果可以能會(huì)遺漏最優(yōu)解。

針對(duì)該問(wèn)題，本文采用混沌粒子群算法(CPSO)、基因表達(dá)式編程(GEP)生成初始解，結(jié)合禁忌局部搜索的協(xié)同模型混合求解算法來(lái)解決多項(xiàng)目調(diào)度問(wèn)題，并通過(guò)改進(jìn)算法縮小理想解與最優(yōu)解的偏差，制定科學(xué)合理的進(jìn)度計(jì)劃。

1 問(wèn)題數(shù)學(xué)模型

MMRCMPSP 主要研究在滿足資源約束以及工序約束的前提下，通過(guò)合理安排工序的開(kāi)始和結(jié)束時(shí)間，來(lái)達(dá)到一定的優(yōu)化目標(biāo)。首先，MMRCMPSP通常涉及若干個(gè)項(xiàng)目、多種作業(yè)模式、一個(gè)共享資源庫(kù)(包含人力資源、任務(wù)工具等可更新資源，作業(yè)材料等不可更新資源)。項(xiàng)目間僅存在資源競(jìng)爭(zhēng)關(guān)系和優(yōu)先級(jí)關(guān)系，不存在不同項(xiàng)目的任務(wù)之間緊前關(guān)系，且所有任務(wù)均需要可更新資源。

其次，由于項(xiàng)目工期往往是項(xiàng)目管理者追求的最主要目標(biāo)，本文選擇最小化項(xiàng)目完工時(shí)間作為模型目標(biāo)函數(shù)。

MMRCMPSP 數(shù)學(xué)模型描述如下:

式中:i為項(xiàng)目編號(hào)，N為項(xiàng)目總數(shù);j為作業(yè)編號(hào)，為項(xiàng)目i 包含的作業(yè)數(shù);為項(xiàng)目權(quán)重;為t 時(shí)刻作業(yè)任務(wù)集合;為項(xiàng)目i 執(zhí)行模式集合;公式(1)表示項(xiàng)目最小執(zhí)行工期;公式(2)表示資源約束;公式(3)表示一個(gè)作業(yè)任務(wù)僅能選擇一個(gè)執(zhí)行模式;公式(4)表示任務(wù)作業(yè)緊前約束;公式(5)表示作業(yè)任務(wù)開(kāi)始時(shí)間大于0。

2 混合算法

MMRCMPSP 問(wèn)題的解由兩個(gè)部分構(gòu)成:用混合算法來(lái)求解優(yōu)化問(wèn)題。其中采用混沌粒子群算法(CPSO)來(lái)優(yōu)化作業(yè)模式組合，基于表達(dá)式編程算法(GEP)來(lái)優(yōu)化解的調(diào)度規(guī)則。為了改進(jìn)由CPSO 和GEP 得到的解的質(zhì)量，每隔固定的次數(shù)，對(duì)每個(gè)個(gè)體解用禁忌搜索算法進(jìn)行局部搜索。嘗試通過(guò)混合算法構(gòu)造調(diào)度規(guī)則，通過(guò)智能搜索方法尋找目標(biāo)函數(shù)最優(yōu)化的一類調(diào)度規(guī)則。

2.1 個(gè)體編碼

粒子采用賈艷［5］中個(gè)體編碼方式，由CPSO 粒子、GEP 染色體合并組成。

(1)CPSO 粒子編碼:粒子中對(duì)應(yīng)N為空間的每一維，其中每一維具體位置對(duì)應(yīng)作業(yè)模式，如圖1 中粒子i。

(2)GEP 染色體編碼:染色體作為項(xiàng)目調(diào)度規(guī)則，由多個(gè)基因組成，如圖1 中染色體i。解決染色體構(gòu)成問(wèn)題，需要定義終結(jié)符、函數(shù)符、基因。

圖1 個(gè)體編碼規(guī)則

定義1 終結(jié)符TS 和函數(shù)符FS。TS={CT，PT，NOP，RN，SRN}，F(xiàn)S={*，+，－，/}，其中CT 表示當(dāng)前調(diào)度時(shí)間;PT 表示該模式作業(yè)工期;NOP 表示作業(yè)緊后作業(yè)數(shù)目;RN 表示單個(gè)作業(yè)所需資源總量;SRN 表示項(xiàng)目中任何作業(yè)對(duì)每種資源最大需求量之和。

定義2 單個(gè)基因組成。基因由頭部和尾部組成，其中頭部長(zhǎng)度為h，尾部長(zhǎng)度為t，通過(guò)公式(6)基礎(chǔ)，parm為函數(shù)最大參數(shù)。h 第一個(gè)位置從FS 選擇，其他位置從FS、TS 中選擇組成頭部。而t 則僅從TS 中選擇組成尾部。

定義3 染色體構(gòu)成。染色體由多個(gè)基因組成，其基因直接通過(guò)運(yùn)算符“+”連接。

2.2 適應(yīng)度評(píng)價(jià)

在混合算法中，適應(yīng)度函數(shù)用來(lái)度量群體中個(gè)體的質(zhì)量。項(xiàng)目調(diào)度目標(biāo)一般是最短項(xiàng)目工期，則適應(yīng)度評(píng)價(jià)函數(shù)可定義為:

2.3 算法流程描述

混合算法執(zhí)行流程如圖2 所示，主要描述流程如下

2.3.1 算法1.混合算法流程

step1.初始化:定義任務(wù)作業(yè)模式，種群規(guī)模N，選擇概率pa，變異概率pb，遷移概率pc，重組概率pd，迭代總數(shù)K，CPSO 最大速度Vmax，最大位置Xmax，種群為P(t)，禁忌執(zhí)行周期ta，令迭代次數(shù)t=1，CPSOGEP 編碼生成初始種群P(1);

step2.產(chǎn)生調(diào)度，解碼染色體，并計(jì)算目標(biāo)函數(shù)，適應(yīng)度評(píng)價(jià)，判斷禁忌條件:若算法滿足，則轉(zhuǎn)step3;否則轉(zhuǎn)step4;

step3.禁忌算法進(jìn)行個(gè)體染色體局部搜索，用適應(yīng)度最優(yōu)個(gè)體替換初始個(gè)體。轉(zhuǎn)step4;

step4.判斷停止條件:若算法停止條件滿足，算法結(jié)束，輸出結(jié)果;否則，轉(zhuǎn)step5;

step5.CPSO 更新模式組合，GEP 染色體產(chǎn)生新種群P(t+1)，令t=t+1，轉(zhuǎn)step2;

在算法1 的步驟1 中，初始化產(chǎn)生初始種群，主要分兩步驟:第一步，CPSO 首先產(chǎn)生作業(yè)模式組合;第二步，GEP 產(chǎn)生染色體，組成種群。具體流程如下。

2.3.2 算法2.初始化生成初始種群

step 1.混沌初始化模式位置和速度;

(1)隨機(jī)產(chǎn)生一個(gè)n 維每個(gè)分量數(shù)值在［0，1］之間的向量，Zi=(Zi1，Zi2，…，Zin)，n為目標(biāo)函數(shù)中的變量個(gè)數(shù)，根據(jù)Logistic 方程，得到N 個(gè)向量;

(2)將Zi的各個(gè)分量載波到對(duì)應(yīng)變量的取值區(qū)間;

(3)計(jì)算粒子群資源需求量，并從N 個(gè)初始群體中選擇資源需求較大的m 個(gè)解作為初始解，隨機(jī)產(chǎn)生n 個(gè)初始速度。

step 2.GEP 根據(jù)模式組合生成染色體，并與模式組合種群個(gè)體;

圖2 混合算法執(zhí)行流程

在算法1 的步驟2 中，基于CPOSGEP 生成調(diào)度規(guī)則，采用PSGS 生成調(diào)度計(jì)劃。

2.3.3 算法3.基于優(yōu)先規(guī)則的多項(xiàng)目啟發(fā)式算法

step1.初始化:任務(wù)作業(yè)集∑J，任務(wù)時(shí)序關(guān)系矩陣P，令當(dāng)前時(shí)間CTg=0，候選集Dg=?，資源R，作業(yè)結(jié)束時(shí)間列表EL;

step2.掃描∑J，判斷是否有未調(diào)用作業(yè):若存在，則轉(zhuǎn)step3;否則，輸出結(jié)果;

step3.時(shí)序約束條件:若滿足，則把該作業(yè)加入Dg;否則，跳過(guò)本步驟;

step4.按照GEP 規(guī)則計(jì)算作業(yè)優(yōu)先權(quán)ρij，按公式(8)結(jié)合項(xiàng)目、項(xiàng)目作業(yè)權(quán)重計(jì)算Dg最終優(yōu)先權(quán);

step5.依據(jù)規(guī)則選擇滿足資源優(yōu)先權(quán)最大作業(yè)，規(guī)則如下:

(1)最大優(yōu)先權(quán)優(yōu)先;

(2)最長(zhǎng)任務(wù)優(yōu)先;

(3)序號(hào)最小任務(wù)優(yōu)先;

step6.判斷資源約束條件:若滿足，則轉(zhuǎn)step7;否則，轉(zhuǎn)step8;

step7.更新資源R，該作業(yè)加入EL，根據(jù)資源重新更新Dg，轉(zhuǎn)step5;

step8.掃描EL，令g=g+1，推進(jìn)時(shí)間;

step9.判斷CT 時(shí)間是否有作業(yè)結(jié)束:若存在，則釋放該作業(yè)占有資源R，更新資源狀態(tài)，轉(zhuǎn)step2;否則轉(zhuǎn)step2。

在算法1 的步驟3 中，采用禁忌搜索幫助GEP算法跳出局部最優(yōu)點(diǎn)，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。

2.3.4 算法4.禁忌搜索

step 1.初始化:令迭代次數(shù)k=0，最大迭代次數(shù)tmaxnum，種群P(t)中的個(gè)體作為初始解，禁忌表H=?，設(shè)置禁忌長(zhǎng)度TL;

step2.僅對(duì)個(gè)體染色體部分采用“2－opt”規(guī)則產(chǎn)生領(lǐng)域N(x)，評(píng)價(jià)適應(yīng)度，選擇較好適應(yīng)度的N(x)k個(gè)作為候選解;

step3.適應(yīng)度最優(yōu)解xbestk，加入禁忌表H，替換xnow，k=k+1;

step4.迭代終止條件:若k≤tmaxnum，則轉(zhuǎn)step2;否則，轉(zhuǎn)step5;

step5.xnow與禁忌表H 最優(yōu)個(gè)體xbest:若F(xnow)＞F(xbest)，則輸出xnow;否則，輸出xbest。轉(zhuǎn)step6;

step6.判斷是否遍歷:若遍歷，則結(jié)束;否則，令k=0，隨機(jī)初始解，轉(zhuǎn)step2;

在算法1 的步驟5 中，采用Logistic 方程對(duì)CPSO 最優(yōu)解進(jìn)行混沌優(yōu)化，并通過(guò)GEP 的選擇復(fù)制、變異、遷移重組等操作更新染色體。具體流程如下。

2.3.5 算法5.CPSOPEG 更新算法

輸入:種群P(t)

輸出:新種群P(t+1)

step1.遍歷種群P(t)，適應(yīng)度優(yōu)于個(gè)體極值pBest，替換pBest;適應(yīng)度優(yōu)于全局gBest，替換gBest;

step2.根據(jù)速度、位置更新粒子速度和位置;

step3.對(duì)全局最優(yōu)位置Pg=(Pg1，Pg2，…，Pgn)進(jìn)行混沌優(yōu)化:

(1)將Pgi映射到Logistic 方程［0，1］中，迭代產(chǎn)生混沌遍歷序列

(3)計(jì)算每一個(gè)可行解Pmg 的適應(yīng)度，得到性能最優(yōu)的解P*，并用該模式取代P(t)中任一個(gè)粒子模式組合;

step4.選擇復(fù)制操作:首先采用精英策略按一定比例保存群中精英作為子代，再通過(guò)二元競(jìng)賽選擇其他個(gè)體作為中間種群;

step5.變異操作:按變異概率Pb中間種群的染色體進(jìn)行變異，產(chǎn)生子代。

step6.遷移和重組操作:

(1)按照IS、RIS、基因遷移概率對(duì)中間種群的染色體部分隨機(jī)選擇進(jìn)行遷移;

(2)按照單點(diǎn)、雙點(diǎn)、基因重組概率中間種群的染色體部分隨機(jī)選擇進(jìn)行重組;

step7.生成新的種群P(t+1)。

3 實(shí)驗(yàn)結(jié)果及分析

目前多項(xiàng)目調(diào)度問(wèn)題，尚缺少公認(rèn)的問(wèn)題庫(kù)。本文采用PSPLIB 問(wèn)題庫(kù)中的c2111_4、c2111_6、j301_3、j301_9 等4 個(gè)實(shí)例，由3 個(gè)作業(yè)模式、2 個(gè)可更新資源、2 個(gè)不可更新資源組成多模式多項(xiàng)目多資源調(diào)度實(shí)例，作業(yè)調(diào)度信息表見(jiàn)表1。其中多項(xiàng) 目 權(quán) 重 系(w1，w2，w3，w4)=(0.2，0.3，0.4，0.1)，可更新資源(r1，r2)=(20，20)。

表1 c21、j30 構(gòu)造的作業(yè)信息表

3.1 實(shí)驗(yàn)環(huán)境

本課題采用硬件平臺(tái)Windows7 操作系統(tǒng)，開(kāi)發(fā)語(yǔ)言JAVA 實(shí)現(xiàn)仿真?；旌纤惴ㄔO(shè)置初始種群N=50，迭代K=60，選擇概率pa=0.3，變異概率pb=0.05，遷移概率pc=0.2，重組概率pd=0.1，禁忌長(zhǎng)度TL=20。10 次運(yùn)行混合算法，選取最優(yōu)解的平均值作為實(shí)驗(yàn)結(jié)果。

3.2 實(shí)驗(yàn)結(jié)果及分析

針對(duì)MMRCMPSP 調(diào)度問(wèn)題，通過(guò)實(shí)驗(yàn)，采用甘特圖表示項(xiàng)目進(jìn)度調(diào)度如圖3 所示?？衫觅Y源R1、R2 消耗情況如圖4、圖5 所示。

圖3 進(jìn)度計(jì)劃甘特圖

圖4 R1 資源利用率

3.3 算法比較

為了檢驗(yàn)本算法的有效性，針對(duì)MMRCMPSP問(wèn)題，運(yùn)用混合算法、遺傳算法GA、混沌粒子群算法CPSO 進(jìn)行比較，以項(xiàng)目調(diào)度工期越小越好，結(jié)果對(duì)比如圖6 所示。

4 結(jié)語(yǔ)

本文針對(duì)MMRCMPSP，考慮多項(xiàng)目完工時(shí)間，建立起多資源多模式約束的多項(xiàng)目調(diào)度的優(yōu)化模型，并進(jìn)行求解。結(jié)果表明通過(guò)對(duì)本問(wèn)題運(yùn)用CPSO 算法對(duì)模式進(jìn)行組合可以避免優(yōu)先規(guī)則確定模式組合可能錯(cuò)失調(diào)度最優(yōu)解;而對(duì)染色體采用禁忌搜索算法，克服遺傳算法常易陷入局部最優(yōu)陷阱，以較快的速度找到最佳的進(jìn)度調(diào)度方案。

圖5 R2 資源利用率

圖6 算法結(jié)果對(duì)比

［1］Goldratt E M，Cox J，Whitford D.The goal:a process of ongoing im-provement［M］.New York:North River Press，1992.

［2］Leach L P.Critical chain project management［M］.Boston:Artech House，2000.

［3］劉士新，宋健海，唐加福.基于關(guān)鍵鏈的資源受限項(xiàng)目調(diào)度新方法［J］.自動(dòng)化學(xué)報(bào)，2006，32(1):60－66.

［4］Cai Z，Li X.A hybrid genetic algorithm for resource-constrained multi-project scheduling problem with resource transfer time［C］// Auto-mation Science and Engineering(CASE)，2012 IEEE International Conference on，IEEE，2012:569－574.

［5］賈艷.資源受限項(xiàng)目調(diào)度問(wèn)題的仿真優(yōu)化方法及其應(yīng)用研究［D］.武漢:華中科技大學(xué)，2012:53－57.

［6］彭京，唐常杰，李川，等.M-GEP:基于多層染色體基因表達(dá)式編程的遺傳進(jìn)化算法［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28(9):1459－1466.

［7］葉春明，潘登，潘逢山.基于混沌粒子群算法的關(guān)鍵鏈項(xiàng)目進(jìn)度管理研究［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(3):890－891，894.

［8］王軍強(qiáng)，張松飛，陳劍，等.一種求解資源受限多項(xiàng)目調(diào)度問(wèn)題的分解算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，19(1):83－96.

［9］張凱.多資源約束下的項(xiàng)目調(diào)度鄰域搜索算法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2014，32(2):123－127.

［10］戴月明，湯繼濤，紀(jì)志成.協(xié)同震蕩搜索混沌粒子群求解資源受限項(xiàng)目調(diào)度問(wèn)題［J］.計(jì)算機(jī)應(yīng)用，2014，34(6):1798－1802.

［11］王偉鑫，王旭，葛顯龍.任務(wù)可拆分的多模式多項(xiàng)目調(diào)度模型與算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2014，20(6):1391－1396.