摘  要： 針對(duì)資源量隨時(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)走的情況非常普遍；對(duì)于機(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算法針對(duì)連續(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ù)對(duì)資源的需求量為常量，第j項(xiàng)任務(wù)對(duì)第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è)偵察蜂。工作蜂在蜜源采蜜,并將蜜源信息帶回，在蜂巢跳舞場(chǎng)以“擺尾舞”的方式與跟隨蜂分享信息，其舞蹈形態(tài)與蜜源的蜂蜜量成正比。跟隨蜂通過觀察工作蜂的舞蹈獲得蜜源信息，然后依據(jù)蜜源的蜂蜜量選擇一個(gè)適當(dāng)?shù)氖澄镌矗妹墼磳?huì)吸引更多的跟隨蜂去采蜜。當(dāng)一個(gè)蜜源被多次采蜜后就會(huì)被拋棄，然后由偵察蜂去勘探一個(gè)新蜜源。蜂群中每一個(gè)工作蜂對(duì)應(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對(duì)應(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ù)排列的食物源位置編碼對(duì)應(yīng)了項(xiàng)目調(diào)度方案，生成候選食物源時(shí)既要保持食物源編碼的離散性又要保持食物源編碼對(duì)應(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)。可以證明，采用這種方法得到的候選食物源滿足項(xiàng)目任務(wù)的先序關(guān)系，是可行調(diào)度[5]。
3.3 適應(yīng)值函數(shù)
    DABC算法中食物源位置編碼唯一對(duì)應(yīng)了一種項(xiàng)目調(diào)度的任務(wù)排列方案，由這一方案可進(jìn)一步得到任務(wù)的時(shí)間安排。時(shí)間安排也是在串行調(diào)度基礎(chǔ)上，遵循在滿足隨時(shí)間變動(dòng)的資源限制的條件下，開始時(shí)間越早越好的原則。這樣就得到了該食物源對(duì)應(yīng)的任務(wù)時(shí)間安排和項(xiàng)目工期。資源時(shí)變的RCPSP的優(yōu)化目標(biāo)是項(xiàng)目工期最短，工期越短意味著調(diào)度方案越好，也就意味著該方案所對(duì)應(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ù)編號(hào)，結(jié)點(diǎn)上方數(shù)字為任務(wù)工期，結(jié)點(diǎn)下方數(shù)字分別為該任務(wù)對(duì)3種資源的使用量。
4.1 DABC求解標(biāo)準(zhǔn)RCPSP
    設(shè)圖4項(xiàng)目的三種資源在單位時(shí)間內(nèi)最大使用限額在整個(gè)項(xiàng)目執(zhí)行期間固定不變，均取為6[6]。首先對(duì)這一標(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ì)算是對(duì)同一項(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)的。
    本文采用一種新的離散人工蜂群算法對(duì)資源隨時(shí)間變化的受限項(xiàng)目調(diào)度優(yōu)化問題進(jìn)行研究，這一問題是對(duì)標(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.