基于蟻群-關(guān)鍵鏈的資源受限項(xiàng)目調(diào)度

宮麗娜

(棗莊學(xué)院 信息科學(xué)與工程學(xué)院,山東棗莊277160)

資源約束下的項(xiàng)目調(diào)度問題 (Resource con-strained proj ect scheduling problem,RCPSP)是一類廣義優(yōu)化問題,主要目的是在滿足項(xiàng)目任務(wù)的緊前關(guān)系和資源約束的條件下,優(yōu)化項(xiàng)目的進(jìn)度安排,從而最小化項(xiàng)目工期.傳統(tǒng)的項(xiàng)目管理方法,如關(guān)鍵路線法 (Critical Path Method,CPM)、計(jì)劃評(píng)審技術(shù) (Program Eval uation and Review Technique,PERT)[1-4]和設(shè)計(jì)結(jié)構(gòu)矩陣 (Design Str uct ure Matrix,DSM),能很好地應(yīng)用于單個(gè)項(xiàng)目的管理,但卻忽視了資源約束的存在.在資源有限的情況下,上述方法已經(jīng)不能有效地對(duì)并行多項(xiàng)目進(jìn)行管理.[5]

1 問題描述

典型資源受限的多項(xiàng)目調(diào)度問題 (Resource—constrained Multi—Project Scheduling Proble m,RCPSP)可以描述如下：在一個(gè)項(xiàng)目組內(nèi)包含N個(gè)相互獨(dú)立的并行項(xiàng)目,共包含D個(gè)任務(wù),該項(xiàng)目組具有兩個(gè)不消耗任何時(shí)間和資源的虛工序：虛擬開始任務(wù)和虛擬結(jié)束任務(wù).第i個(gè)項(xiàng)目包含ni個(gè)任務(wù),這N個(gè)項(xiàng)目共享K種可更新資源,其中第k種資源的容量為Rk.用Aij表示第i個(gè)項(xiàng)目中的第j個(gè)任務(wù),其工期為dij,對(duì)第k種資源的需求量為rijk,任務(wù)的開始時(shí)間標(biāo)記為Sij,結(jié)束時(shí)間標(biāo)記為fij,它的所有緊前任務(wù)形成的集合記為Pij,用ai表示第i個(gè)項(xiàng)目的權(quán)重,在時(shí)間t時(shí)正在進(jìn)行的所有任務(wù)的集合標(biāo)記為It.綜合上述假設(shè)和采用的符號(hào),可以描述為以下形式：

其中：Fi是第i個(gè)項(xiàng)目的完成時(shí)間.式 (1)表示目標(biāo)函數(shù)代表項(xiàng)目組的總工期最短,需要通過優(yōu)化使該項(xiàng)目標(biāo)函數(shù)最小;式 (2)表示了任務(wù)間的緊前關(guān)系,一個(gè)任務(wù)沒有完成之前不能開始它的任何后續(xù)任務(wù);式 (3)則表示在任意時(shí)刻所有項(xiàng)目正在執(zhí)行的任務(wù)對(duì)每種資源的需求總量不得超過該資源的總量.

對(duì)于多個(gè)項(xiàng)目中任務(wù)調(diào)度的確定,首先將各個(gè)項(xiàng)目的網(wǎng)結(jié)構(gòu)圖通過增加虛擬節(jié)點(diǎn),合并為一個(gè)單一的網(wǎng)絡(luò)結(jié)構(gòu)圖,這并不改變每個(gè)項(xiàng)目中任務(wù)間的關(guān)系,也不是對(duì)各個(gè)項(xiàng)目進(jìn)行整合,而是各個(gè)項(xiàng)目的任務(wù)在整個(gè)新網(wǎng)絡(luò)圖中重新進(jìn)行唯一標(biāo)示.網(wǎng)絡(luò)圖增加兩個(gè)不消耗任何時(shí)間和資源的虛擬節(jié)點(diǎn)用于標(biāo)示整個(gè)設(shè)計(jì)過程的開始和結(jié)束：虛擬開始節(jié)點(diǎn)S和虛擬結(jié)束節(jié)點(diǎn)E作為整個(gè)設(shè)計(jì)過程唯一的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn).

2 蟻群-關(guān)鍵鏈算法

2.1 蟻群優(yōu)化算法 (ACO)

蟻群算法 (Ant Colony Opti mization)是由意大利學(xué)者Dorigo等人在20世紀(jì)90年代初首先提出來的.蟻群算法設(shè)計(jì)虛擬 “螞蟻”,讓他們摸索不同路線,并留下會(huì)隨時(shí)間逐漸消失的虛擬 “信息素”.根據(jù) “信息素較濃的路線更近”的原則,即可選擇出最佳的路線.

通過蟻群算法構(gòu)造的任務(wù)列表I=(l0,l1,…,ln+1)(其中n=ni),任務(wù)是逐個(gè)的被分配到列表I從l0到ln+1,所以每個(gè)分配可以代表螞蟻的一次決策.當(dāng)活動(dòng)lr分配到列表I的r位置時(shí),后序集Nr包含了這些活動(dòng),這些活動(dòng)的緊前任務(wù)已經(jīng)分配到列表中.這些后序集在構(gòu)建列表過程中是逐步被修改的.在構(gòu)建活動(dòng)列表過程中,螞蟻先分配l0=0,然后在每一階段,螞蟻都要利用信息素和啟發(fā)信息在后序集Nr里選擇一個(gè)活動(dòng)j,使lr=j;從r=0決策到r=n.很明顯,通過ACO構(gòu)建的活動(dòng)列表遵守優(yōu)先可行性.而且當(dāng)r-1個(gè)活動(dòng)被選擇的同時(shí),也安排了這些活動(dòng)的開始時(shí)間、結(jié)束時(shí)間以及分配給它們的資源.

2.1.2 算法描述

在每一代中存在著m個(gè)螞蟻,每個(gè)螞蟻都生成一個(gè)解決方案,即一個(gè)有序的活動(dòng)列表,然后根據(jù)這個(gè)活動(dòng)列表應(yīng)用串行調(diào)度生成算法,生成調(diào)度方案.

在第一代生成時(shí),初始化所有活動(dòng)的信息素為1,然后根據(jù)啟發(fā)信息和信息素的一定比例來生成活動(dòng)轉(zhuǎn)移概率.其中后序列表中轉(zhuǎn)移概率大的被選入到活動(dòng)列表.當(dāng)?shù)谝淮Y(jié)束后,以后的每代對(duì)活動(dòng)的信息素進(jìn)行本地更新、蒸發(fā)和全局更新,然后進(jìn)行尋找,直到找到合適的活動(dòng)列表位置.

具體算法如下：

初始化

Loop

把蟻群中所有螞蟻置于開始活動(dòng)處

Loop

For 每個(gè)螞蟻

構(gòu)造可行活動(dòng)集合

對(duì)活動(dòng)集合中的活動(dòng)進(jìn)行計(jì)算,選擇下一個(gè)活動(dòng)

根據(jù)公式 (2)對(duì)信息素進(jìn)行本地更新

將活動(dòng)加入活動(dòng)列表

Next

Until所有的螞蟻都構(gòu)造了一個(gè)完全可行解

使用串行調(diào)度生成方案求出每個(gè)可行解的工期

進(jìn)行信息蒸發(fā)和全局信息素更新

Until滿足停機(jī)條件

2.2 關(guān)鍵鏈調(diào)度方法

關(guān)鍵鏈管理方法采用關(guān)鍵鏈代替關(guān)鍵路徑.但針對(duì)一個(gè)RCPSP,關(guān)鍵鏈數(shù)量、長(zhǎng)度以及關(guān)鍵鏈上包含的工作集合均決定于RCPSP的求解過程.

應(yīng)用關(guān)鍵鏈方法需要解決以下問題：1)活動(dòng)時(shí)間消減的系數(shù);2)在關(guān)鍵鏈的活動(dòng)中設(shè)置緩存問題.

針對(duì)第一個(gè)問題,主要是應(yīng)用在不受資源限制時(shí)項(xiàng)目的完成時(shí)間T1和受資源限制時(shí)資源的完成時(shí)間T2的比值來對(duì)活動(dòng)時(shí)間進(jìn)行消減,并且只消減關(guān)鍵鏈上的活動(dòng)時(shí)間.[6]與使用50%的剪貼法比,使用比值的方法進(jìn)行消減,使得項(xiàng)目活動(dòng)是根據(jù)項(xiàng)目的具體情況進(jìn)行消減的,更有效地正確估算出項(xiàng)目的完工時(shí)間.

針對(duì)第二個(gè)問題,對(duì)于資源緩存、對(duì)于關(guān)鍵鏈上每個(gè)活動(dòng)的緩存可采用如下公式：

其中F.Tm表示緩存的大小,表示有資源限制時(shí)的活動(dòng)時(shí)間,表示沒有資源限制時(shí)的活動(dòng)時(shí)間.

而對(duì)于全局的緩存可以采用如下公式：

與此同時(shí),本文還引入了兩個(gè)變量系數(shù)：項(xiàng)目靈活系數(shù)Kp和活動(dòng)靈活系數(shù),用于更準(zhǔn)確地確定項(xiàng)目的完工時(shí)間.

a)如果資源限制是由于政策因素,如由于機(jī)器太貴而決定自己生產(chǎn)機(jī)器等,則項(xiàng)目靈活系數(shù)就可以用來改變項(xiàng)目活動(dòng)時(shí)間.

如果Kp＞0,則表明考慮到戰(zhàn)略上的原因,項(xiàng)目的完工時(shí)間需要延長(zhǎng).于是,會(huì)得到下面的式子：

如果Kp＜0,則表明通過其他方法來縮短完工時(shí)間,比如增加新員工.可以得到如下式子：

b)基于項(xiàng)目自身的特點(diǎn),活動(dòng)靈活系數(shù)可以應(yīng)用于關(guān)鍵鏈的活動(dòng)中來調(diào)整活動(dòng)時(shí)間.通過修改,項(xiàng)目的完工時(shí)間可用如下公式表示：

2.3 具體算法描述

在此主要介紹具體的執(zhí)行算法.

第一步：計(jì)算沒有資源限制時(shí)的完工時(shí)間T1,利用蟻群算法計(jì)算資源限制時(shí)項(xiàng)目的完工時(shí)間T2和關(guān)鍵鏈;

第二步：計(jì)算關(guān)鍵鏈活動(dòng)的消減系數(shù)CR=T1/T2,并對(duì)活動(dòng)時(shí)間進(jìn)行消減;

第三步：利用項(xiàng)目靈活系數(shù)和活動(dòng)靈活系數(shù)對(duì)項(xiàng)目的關(guān)鍵鏈完工時(shí)間進(jìn)行調(diào)整;

第四步：在關(guān)鍵鏈活動(dòng)的前邊設(shè)置資源緩存.

3 實(shí)例分析

為了分析算法的有效性,采用文獻(xiàn) [7]的實(shí)例加以驗(yàn)證,其網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示.節(jié)點(diǎn)處的二元組分別表示工序最可能持續(xù)時(shí)間、資源R1的需求量.R1可使用量為3個(gè)單位,且工序中資源需求是不可分的.

步驟1 在資源不受限制時(shí),關(guān)鍵路徑為A→D→G,項(xiàng)目完成時(shí)間T1=9;在資源受限時(shí),應(yīng)用第三部分的蟻群算法得到關(guān)鍵鏈為：A→B→D→G→H;項(xiàng)目的完成時(shí)間T2=15;

步驟2 消減系數(shù)C2=T1/T2=9/15=60%,則得到新的項(xiàng)目網(wǎng)絡(luò)如圖2所示,項(xiàng)目完工時(shí)間為9;

步驟3 利用項(xiàng)目或者活動(dòng)的靈活系數(shù)對(duì)項(xiàng)目或者活動(dòng)時(shí)間進(jìn)行調(diào)整.對(duì)于一般是利用活動(dòng)在項(xiàng)目中的重要性及活動(dòng)本身的簡(jiǎn)單性來定義的.一般取重要性和簡(jiǎn)單性系數(shù)的最大值.假設(shè)=1、=0.75=0.5、.6、=0.75,那么,項(xiàng)目的完成時(shí)間T=9+(2-1.2)×1+(3.5-2.1)×0.75+(3.5-2.1)×0.5+(3.5-2.1)×0.6+(2.5-1.5)×0.75=9+0.8+1.05+0.7+0.84+0.75=13.2;通過修改得到的項(xiàng)目網(wǎng)絡(luò)如圖3所示;

圖1 項(xiàng)目網(wǎng)絡(luò)圖

圖2 消減后的項(xiàng)目網(wǎng)絡(luò)圖

圖3 修改后的項(xiàng)目網(wǎng)絡(luò)圖

步驟4 設(shè)置緩存.得到的最后結(jié)果如圖3所示.

總之,資源約束下的多項(xiàng)目調(diào)度的算法是先通過蟻群算法找到一個(gè)合適的解,然后通過關(guān)鍵鏈的方法對(duì)可優(yōu)解進(jìn)行調(diào)整,以便準(zhǔn)確地估計(jì)出項(xiàng)目的完工時(shí)間,主要有以下優(yōu)點(diǎn)：

1)對(duì)于蟻群算法的啟發(fā)信息主要采用了資源利用率改變量的方法;

2)用蟻群算法在安排活動(dòng)時(shí),對(duì)于具有相同活動(dòng)時(shí)間的兩個(gè)活動(dòng)可以同時(shí)進(jìn)行安排;

3)對(duì)于關(guān)鍵鏈的活動(dòng)時(shí)間消減系數(shù)采用了用沒有資源限制的時(shí)間T 1和有資源限制的時(shí)間T 2的比值的方法.

[1]BERMAN E B.Resource allocation in a PERT net wor k under continuous activity ti me-cost f unction[J].Manage ment Science,1964(10)：734-745.

[2]ROBILLARD P.Expected co mpletion ti me in PERT net works[J].Operations Research,1976,24：177-182.

[3]LA WRENCE P,JEFFERY K.Cochran A new co mputational appr oach f or pr oject management net wor ks[J].Co mputers ind.Engng,1995,29：339-343.

[4]FATEMI GHOMI S M T,RABBANI M.A new str uct ural mechanis mfor reducibility of stochastic PERT net wor ks[J].Eur opean Jour nal of Operational Research,2003,145：394-402.

[5]施淑洪,鄭榮良.電動(dòng)助力轉(zhuǎn)向系統(tǒng)及系統(tǒng)模型分析 [J].江蘇大學(xué)學(xué)報(bào)：自然科學(xué)版,2002,23(5)：57-60.

[6]Chiu-Chi Weia,Ping-Hung Liub,Ying-Chin Tsaic.Resource-constrained pr oject management using enhanced t heory of constraint[J].International Journal of Project Management,2002,20：561-567.

[7]張靜文,胡信布,王茉琴.關(guān)鍵鏈項(xiàng)目計(jì)劃調(diào)度方法研究 [J].科技管理研究,2008(3)：280-283.