多模式多資源約束下的多項目調度混合算法＊

王 南，馬 永，陳笑蓉

(1.廣州市地下鐵道總公司，廣東 廣州 510180;2.貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

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

傳統(tǒng)多項目管理中，基于Gold 博士的約束理論［1］，開啟項目調度研究新方法。Leach［2］對于優(yōu)先權項目進行管理，重點是找出多項目共享關鍵資源約束。劉士新［3］建立多目標首先資源項目優(yōu)化調度模式，采用基于關鍵鏈項目調度的優(yōu)先規(guī)則啟發(fā)式算法。Cai Z［4］等提出了混合遺傳算法求解方法。賈艷［5］針對多模式單項目提出了粒子群基因表達式編程混合算法對調度規(guī)則求解。彭京［6］等提出了基于多層染色體基因表達式編程的遺傳進化算法。葉春明［7］等將建立混沌粒子群算法尋找關鍵鏈項目進度調度。王軍強［8］等通過建立蟻群算法、資源調度模型，對多項目的時序約束、資源約束多目標調度的分解求解方法。張凱［9］基于拓撲排序的鄰域搜索算法模型能夠針對單項目實例找到較優(yōu)解。而戴月明［10］等則建立協同震蕩搜索混沌粒子群對首先項目調度研究。王偉鑫［11］等通過建立云遺傳算法對全局搜索、快速收斂有比較好的效果。對于多模式調度通常采用優(yōu)先權方法，調度的結果可以能會遺漏最優(yōu)解。

針對該問題，本文采用混沌粒子群算法(CPSO)、基因表達式編程(GEP)生成初始解，結合禁忌局部搜索的協同模型混合求解算法來解決多項目調度問題，并通過改進算法縮小理想解與最優(yōu)解的偏差，制定科學合理的進度計劃。

1 問題數學模型

MMRCMPSP 主要研究在滿足資源約束以及工序約束的前提下，通過合理安排工序的開始和結束時間，來達到一定的優(yōu)化目標。首先，MMRCMPSP通常涉及若干個項目、多種作業(yè)模式、一個共享資源庫(包含人力資源、任務工具等可更新資源，作業(yè)材料等不可更新資源)。項目間僅存在資源競爭關系和優(yōu)先級關系，不存在不同項目的任務之間緊前關系，且所有任務均需要可更新資源。

其次，由于項目工期往往是項目管理者追求的最主要目標，本文選擇最小化項目完工時間作為模型目標函數。

MMRCMPSP 數學模型描述如下:

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

2 混合算法

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

2.1 個體編碼

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

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

(2)GEP 染色體編碼:染色體作為項目調度規(guī)則，由多個基因組成，如圖1 中染色體i。解決染色體構成問題，需要定義終結符、函數符、基因。

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

定義1 終結符TS 和函數符FS。TS={CT，PT，NOP，RN，SRN}，FS={*，+，－，/}，其中CT 表示當前調度時間;PT 表示該模式作業(yè)工期;NOP 表示作業(yè)緊后作業(yè)數目;RN 表示單個作業(yè)所需資源總量;SRN 表示項目中任何作業(yè)對每種資源最大需求量之和。

定義2 單個基因組成?；蛴深^部和尾部組成，其中頭部長度為h，尾部長度為t，通過公式(6)基礎，parm為函數最大參數。h 第一個位置從FS 選擇，其他位置從FS、TS 中選擇組成頭部。而t 則僅從TS 中選擇組成尾部。

定義3 染色體構成。染色體由多個基因組成，其基因直接通過運算符“+”連接。

2.2 適應度評價

在混合算法中，適應度函數用來度量群體中個體的質量。項目調度目標一般是最短項目工期，則適應度評價函數可定義為:

2.3 算法流程描述

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

2.3.1 算法1.混合算法流程

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

step2.產生調度，解碼染色體，并計算目標函數，適應度評價，判斷禁忌條件:若算法滿足，則轉step3;否則轉step4;

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

step4.判斷停止條件:若算法停止條件滿足，算法結束，輸出結果;否則，轉step5;

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

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

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

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

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

(2)將Zi的各個分量載波到對應變量的取值區(qū)間;

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

step 2.GEP 根據模式組合生成染色體，并與模式組合種群個體;

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

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

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

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

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

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

step4.按照GEP 規(guī)則計算作業(yè)優(yōu)先權ρij，按公式(8)結合項目、項目作業(yè)權重計算Dg最終優(yōu)先權;

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

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

(2)最長任務優(yōu)先;

(3)序號最小任務優(yōu)先;

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

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

step8.掃描EL，令g=g+1，推進時間;

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

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

2.3.4 算法4.禁忌搜索

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

step2.僅對個體染色體部分采用“2－opt”規(guī)則產生領域N(x)，評價適應度，選擇較好適應度的N(x)k個作為候選解;

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

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

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

step6.判斷是否遍歷:若遍歷，則結束;否則，令k=0，隨機初始解，轉step2;

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

2.3.5 算法5.CPSOPEG 更新算法

輸入:種群P(t)

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

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

step2.根據速度、位置更新粒子速度和位置;

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

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

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

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

step5.變異操作:按變異概率Pb中間種群的染色體進行變異，產生子代。

step6.遷移和重組操作:

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

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

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

3 實驗結果及分析

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

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

3.1 實驗環(huán)境

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

3.2 實驗結果及分析

針對MMRCMPSP 調度問題，通過實驗，采用甘特圖表示項目進度調度如圖3 所示?？衫觅Y源R1、R2 消耗情況如圖4、圖5 所示。

圖3 進度計劃甘特圖

圖4 R1 資源利用率

3.3 算法比較

為了檢驗本算法的有效性，針對MMRCMPSP問題，運用混合算法、遺傳算法GA、混沌粒子群算法CPSO 進行比較，以項目調度工期越小越好，結果對比如圖6 所示。

4 結語

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

圖5 R2 資源利用率

圖6 算法結果對比

［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］劉士新，宋健海，唐加福.基于關鍵鏈的資源受限項目調度新方法［J］.自動化學報，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］賈艷.資源受限項目調度問題的仿真優(yōu)化方法及其應用研究［D］.武漢:華中科技大學，2012:53－57.

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

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

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

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

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

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