摘  要： 針對資源量隨時(shí)間變動(dòng)的項(xiàng)目調(diào)度問題提出了一種新的離散人工蜂群求解算法,。算法食物源的位置采用基于任務(wù)排列的編碼方法,，并提出一種可以保持解的離散性和可行性的候選食物源生成方法,。仿真結(jié)果表明，該算法能有效地求解資源時(shí)變的受限項(xiàng)目調(diào)度問題,，研究發(fā)現(xiàn)在保持資源總量不變甚至減少的情況下,，通過調(diào)整資源配置能夠顯著縮短項(xiàng)目工期，可見資源配置優(yōu)化在項(xiàng)目管理中的重要作用,。
關(guān)鍵詞： 項(xiàng)目調(diào)度,；資源量隨時(shí)間變動(dòng)；人工蜂群算法,；離散

    自上世紀(jì)60年代以來,，資源受限項(xiàng)目調(diào)度問題RCPSP(Resource-Constrained Project Scheduling)引起了國內(nèi)外學(xué)者的極大關(guān)注，RCPSP是指在滿足資源約束和任務(wù)先序關(guān)系條件下,，合理安排調(diào)度,，以實(shí)現(xiàn)項(xiàng)目的既定目標(biāo)最優(yōu)（通常為項(xiàng)目工期最短）。目前,，標(biāo)準(zhǔn)RCPSP已經(jīng)成為運(yùn)籌學(xué)領(lǐng)域的一個(gè)經(jīng)典問題,，它建立在一定假設(shè)之上，如假定項(xiàng)目的可用資源均為可更新資源,，資源的最大可用量在整個(gè)項(xiàng)目執(zhí)行期間已知且保持不變,。而實(shí)際項(xiàng)目中可用資源量卻經(jīng)常是隨時(shí)間變化的。以人力資源為例,，由于組織或多項(xiàng)目間的需要,，在項(xiàng)目執(zhí)行過程中人員被借用來或抽調(diào)走的情況非常普遍；對于機(jī)械設(shè)備等資源,，在不同的項(xiàng)目間被來回占用的情況更是常見,。這種資源量隨時(shí)間變動(dòng)的項(xiàng)目調(diào)度問題是標(biāo)準(zhǔn)RCPSP的一個(gè)擴(kuò)展和補(bǔ)充，它更符合許多項(xiàng)目資源配置的實(shí)際情況,。Klein[1]采用禁忌搜索算法求解了資源量變動(dòng)需求固定的RCPSP問題,。Hartmann[2]描述了一個(gè)真實(shí)醫(yī)療科研項(xiàng)目，項(xiàng)目中每個(gè)活動(dòng)僅在活動(dòng)執(zhí)行的最后時(shí)期需要醫(yī)療設(shè)備,，且研究人員和實(shí)驗(yàn)設(shè)備這兩種資源量是變動(dòng)的,。
    RCPSP在組合優(yōu)化中屬于NP-hard問題，其求解方法分為精確算法和啟發(fā)式算法兩大類,。由于啟發(fā)式算法與精確算法相比,，操作簡便靈活，易于移植,，同時(shí)近年來先進(jìn)進(jìn)化算法和智能算法不斷涌現(xiàn),，應(yīng)用與智能算法相結(jié)合的啟發(fā)式算法來求解RCPSP受到更多學(xué)者的青睞,。2005年,，Karaboga[3]提出了一種人工蜂群算法ABC(Artificial Bee Colony),，用以解決連續(xù)型多峰函數(shù)尋優(yōu)問題。Akbari[4]等用ABC算法求解了基于優(yōu)先權(quán)的標(biāo)準(zhǔn)RCPSP,。不足之處在于,，ABC算法針對連續(xù)性優(yōu)化問題提出，參考文獻(xiàn)[4]在求解RCPSP時(shí)也是按連續(xù)型問題進(jìn)行處理的,，沒有考慮解的離散性特點(diǎn),。
    本文在研究資源量隨時(shí)間變動(dòng)的RCPSP解的特點(diǎn)的基礎(chǔ)上，提出了一種基于任務(wù)排列的離散的食物源編碼方法,，進(jìn)而通過離散人工蜂群算法DABC（Discrete Artificial Bee Colony）求解項(xiàng)目的優(yōu)化調(diào)度方案,。
1 問題描述
    資源時(shí)變的RCPSP可描述如下：設(shè)項(xiàng)目的任務(wù)集為J={0,1,2,…,n,n+1}，任務(wù)工時(shí)已知且任務(wù)不可拆分,，任務(wù)0和任務(wù)n+1為虛任務(wù),，工期為0,分別代表開始任務(wù)和結(jié)束任務(wù)。sj,、fj,、dj分別表示第j項(xiàng)任務(wù)的開始時(shí)間、結(jié)束時(shí)間和總耗時(shí),，其中sj=fj-dj,。每項(xiàng)任務(wù)必須在其所有的緊前任務(wù)完成后方能開始，Pj為任務(wù)j的緊前任務(wù)集合,。設(shè)項(xiàng)目共有K種可更新資源,，每種可用資源的最大限額隨項(xiàng)目執(zhí)行的時(shí)間而變化，則第k種資源在t時(shí)刻的最大可用限額為Rkt,，t為項(xiàng)目執(zhí)行中的每一時(shí)刻（t=1,，2，…,，T）,，T為項(xiàng)目工期。每個(gè)任務(wù)對資源的需求量為常量,，第j項(xiàng)任務(wù)對第k種資源的需求量為rjk,。A(t)代表t時(shí)刻正在執(zhí)行的任務(wù)的集合。項(xiàng)目調(diào)度的優(yōu)化目標(biāo)是項(xiàng)目工期最短,，則建立該問題的數(shù)學(xué)模型為：

2 人工蜂群算法的基本原理
    ABC算法是一種模擬自然蜜蜂覓食中群體智能行為的元啟發(fā)算法,。該算法中人工蜂群包含三類蜂[3]：工作蜂、跟隨蜂和偵察蜂,。蜂群按數(shù)量等分成兩組,，前一半是工作蜂，后一半是跟隨蜂,，另設(shè)一個(gè)偵察蜂,。工作蜂在蜜源采蜜,并將蜜源信息帶回,，在蜂巢跳舞場以“擺尾舞”的方式與跟隨蜂分享信息，其舞蹈形態(tài)與蜜源的蜂蜜量成正比,。跟隨蜂通過觀察工作蜂的舞蹈獲得蜜源信息,，然后依據(jù)蜜源的蜂蜜量選擇一個(gè)適當(dāng)?shù)氖澄镌矗妹墼磳?huì)吸引更多的跟隨蜂去采蜜,。當(dāng)一個(gè)蜜源被多次采蜜后就會(huì)被拋棄,，然后由偵察蜂去勘探一個(gè)新蜜源。蜂群中每一個(gè)工作蜂對應(yīng)一個(gè)食物源,，即蜜源,，每個(gè)食物源的位置代表優(yōu)化問題的一個(gè)可行解，食物源的蜂蜜量稱為適應(yīng)值,，適應(yīng)值的大小表征相關(guān)解的質(zhì)量,。適應(yīng)值越大，蜂蜜量越多,，解的質(zhì)量越好,。ABC算法的簡明步驟如下：
    (1)人工蜂群的初始化
    (2)迭代
    ①將人工蜂放置到食物源采蜜；
    ②將跟隨蜂放置到食物源采蜜,；
    ③派偵察蜂尋找新的食物源,；
    ④更新目前為止找到的最好食物源。
    (3)停止(滿足迭代停止條件)
     工作蜂有SN個(gè),，xi是一個(gè)D維向量,，代表工作蜂i對應(yīng)的食物源。每次迭代工作蜂i在原食物源xi的基礎(chǔ)上再生成候選食物源vi,，候選食物源vi由下式生成：
 
    初始食物源的位置需要通過調(diào)度生成機(jī)制產(chǎn)生可行調(diào)度方案,。本文采用改進(jìn)的串行調(diào)度生成機(jī)制來生成初始食物源。改進(jìn)的串行調(diào)度包含l=1,，2,，…，n個(gè)階段,，每個(gè)階段在先序任務(wù)已處理完的待處理任務(wù)集合中隨機(jī)地選擇一個(gè)任務(wù)并安排其執(zhí)行時(shí)間,，任務(wù)安排遵循在滿足隨時(shí)間變動(dòng)的資源限制的條件下開始時(shí)間越早越好的原則。

3.2 候選食物源的生成
    ABC算法中候選食物源的生成方式是優(yōu)化效果和效率好壞的關(guān)鍵,。本文基于任務(wù)排列的食物源位置編碼對應(yīng)了項(xiàng)目調(diào)度方案,，生成候選食物源時(shí)既要保持食物源編碼的離散性又要保持食物源編碼對應(yīng)的調(diào)度方案的可行性，為此本文采用了一種新的候選食物源生成方法,。
    仍以圖1所示項(xiàng)目為例來說明候選食物源的生成方法,，設(shè)食物源xi=(1，2，4,，5,，3，6),，選定的相鄰食物源xk=(1，3,，2,，4，5,，6),，隨機(jī)生成一位d=3。則候選食物源vi的生成方法為：vi的前兩個(gè)元素取xi的前兩個(gè)元素(1,，2),，去除xk中與xi的前兩個(gè)元素相同的元素即得(3，4,，5,，6)，取該矩陣中第一個(gè)元素為vi的第三個(gè)元素,，則vi的前三個(gè)元素取為(1,，2，3),，再從xi中去除(1,，2，3)得到(4,，5,，6)作為vi的后三個(gè)元素。這樣得到vi=(1,，2,，
3，4,，5,，6)?？梢宰C明,，采用這種方法得到的候選食物源滿足項(xiàng)目任務(wù)的先序關(guān)系，是可行調(diào)度[5],。
3.3 適應(yīng)值函數(shù)
    DABC算法中食物源位置編碼唯一對應(yīng)了一種項(xiàng)目調(diào)度的任務(wù)排列方案,，由這一方案可進(jìn)一步得到任務(wù)的時(shí)間安排。時(shí)間安排也是在串行調(diào)度基礎(chǔ)上，遵循在滿足隨時(shí)間變動(dòng)的資源限制的條件下,，開始時(shí)間越早越好的原則,。這樣就得到了該食物源對應(yīng)的任務(wù)時(shí)間安排和項(xiàng)目工期。資源時(shí)變的RCPSP的優(yōu)化目標(biāo)是項(xiàng)目工期最短,，工期越短意味著調(diào)度方案越好,，也就意味著該方案所對應(yīng)的食物源蜂蜜量越多，適應(yīng)值越大,。因此ABC算法中食物源xi的適應(yīng)值fiti可由式(4)得到：
  
3.4 DABC算法的基本框架
    基于上述原理,，求解資源時(shí)變的RCPSP的DABC算法實(shí)現(xiàn)的基本框架如圖3所示。
4 算例仿真
    為了驗(yàn)證DABC算法求解資源隨時(shí)間變動(dòng)的RCPSP的有效性,，本文選取了一個(gè)有27個(gè)任務(wù)的項(xiàng)目算例[6],。如圖4所示，任務(wù)0和任務(wù)26為虛任務(wù),，項(xiàng)目的可更新資源種類為3種,，圖中結(jié)點(diǎn)圓圈內(nèi)數(shù)字為任務(wù)編號，結(jié)點(diǎn)上方數(shù)字為任務(wù)工期,，結(jié)點(diǎn)下方數(shù)字分別為該任務(wù)對3種資源的使用量,。
4.1 DABC求解標(biāo)準(zhǔn)RCPSP
    設(shè)圖4項(xiàng)目的三種資源在單位時(shí)間內(nèi)最大使用限額在整個(gè)項(xiàng)目執(zhí)行期間固定不變，均取為6[6],。首先對這一標(biāo)準(zhǔn)RCPSP問題進(jìn)行驗(yàn)證計(jì)算,。本文用ABC與DABC兩種算法進(jìn)行計(jì)算，圖5給出了在10次仿真實(shí)驗(yàn)中平均優(yōu)化過程,，算法中蜂群數(shù)量NP=30,，即食物源SN=15，最大迭代次數(shù)Cmax=200,，trailmax=3,。另外，ABC算法工作蜂生成候選食物源應(yīng)用式(2)時(shí)取參數(shù)1=2,，跟隨蜂尋找候選食物源應(yīng)用式(2)時(shí),，取參數(shù)?棕2=3。兩種算法得到的項(xiàng)目工期的最優(yōu)解均為64天,，同時(shí)在最優(yōu)工期下可以得到多種最優(yōu)調(diào)度方案,。優(yōu)化結(jié)果與參考文獻(xiàn)[6]一致。由圖5可以看出DABC算法能很好地保持種群的多樣性,，優(yōu)化效果要好于ABC算法,，同時(shí)運(yùn)算速度也要比ABC算法快。

    由DABC算法得到在項(xiàng)目工期為64時(shí)最優(yōu)食物源編碼為[1,2,5,3,7,4,6,8,10,11,13,15,18,9,22,19,14,12,23,
17,16,20,21,24,25],，此時(shí)三種資源的利用情況如圖6所示,。

得到滿足。
4.3 結(jié)果分析
    章節(jié)4.1和章節(jié)4.2的計(jì)算是對同一項(xiàng)目在不同資源配置情況下得到的優(yōu)化調(diào)度方案。前者中項(xiàng)目三種資源的總可用量為[384,384,384],，后者中項(xiàng)目三種資源的總可用量為[345,326,321],。從資源配置來看，前者中各種資源可用總量都要比后者的大,，但是后者資源配置方法卻使得項(xiàng)目工期縮短了整整20天,，比前者完工期提前了31.25%。
    由此可知,，在資源總量保持不變甚至減少的情況下,，通過調(diào)整資源在項(xiàng)目執(zhí)行期間的配置情況，可以有效地縮短項(xiàng)目工期,。這種調(diào)整資源配置的方法在實(shí)際項(xiàng)目的運(yùn)作中無疑是可以操作和實(shí)現(xiàn)的。
    本文采用一種新的離散人工蜂群算法對資源隨時(shí)間變化的受限項(xiàng)目調(diào)度優(yōu)化問題進(jìn)行研究,，這一問題是對標(biāo)準(zhǔn)RCPSP的必要補(bǔ)充和擴(kuò)展,。通過實(shí)例仿真可以得到如下結(jié)論：第一，本文所提出的DABC算法能有效地求解資源量隨時(shí)間變動(dòng)的RCPSP和標(biāo)準(zhǔn)RCPSP,，比ABC算法有更好的收斂特性,；第二，資源時(shí)變的RCPSP更符合項(xiàng)目實(shí)際,，通過調(diào)整資源在項(xiàng)目執(zhí)行中的配置情況,，可以在保持可用資源總量不變或減少的情況下顯著地縮短項(xiàng)目工期，提高資源利用率,。這一結(jié)論在今后項(xiàng)目管理中應(yīng)給予充分的重視,。
參考文獻(xiàn)
[1] KLEIN R.Project scheduling with time-varying resource  constraints[J].International Journal of Production Research, 2000,38(16):3937-3952.
[2] HARTMANN S.Project scheduling under limited resources: Models, methods, and applications[M].Springer,Berlin, Germany,Lecture Notes in Economics and Mathematical   Systems，1999:221.
[3] KARABOGA D.An idea based on honey bee swarm for  numerical optimization[R].Technical Report-TRO6, 2005.
[4] AKBARI R, ZEIGHAMI V, ZIARATI K.Artificial bee  colony for resource constrained project scheduling problem [J].International Journal of Industrial Engineering Computations,2011,2(1): 45-60.
[5] HARTMANN S.A competitive genetic algorithm for  resource-constrained project scheduling[J].Naval Research Logistics, 1998,45(7):733-750.
[6] Zhang Hong, Li Heng, TAM C M.Particle swarm optimization for resource-constrained project scheduling[J].International Journal of Project Management 2006,24(1):83-92.