摘 要： 針對資源量隨時間變動的項目調度問題提出了一種新的離散人工蜂群求解算法。算法食物源的位置采用基于任務排列的編碼方法，并提出一種可以保持解的離散性和可行性的候選食物源生成方法。仿真結果表明，該算法能有效地求解資源時變的受限項目調度問題，研究發(fā)現(xiàn)在保持資源總量不變甚至減少的情況下，通過調整資源配置能夠顯著縮短項目工期，可見資源配置優(yōu)化在項目管理中的重要作用。
關鍵詞： 項目調度；資源量隨時間變動；人工蜂群算法；離散
自上世紀60年代以來，資源受限項目調度問題RCPSP(Resource-Constrained Project Scheduling)引起了國內外學者的極大關注，RCPSP是指在滿足資源約束和任務先序關系條件下，合理安排調度，以實現(xiàn)項目的既定目標最優(yōu)（通常為項目工期最短）。目前，標準RCPSP已經成為運籌學領域的一個經典問題，它建立在一定假設之上，如假定項目的可用資源均為可更新資源，資源的最大可用量在整個項目執(zhí)行期間已知且保持不變。而實際項目中可用資源量卻經常是隨時間變化的。以人力資源為例，由于組織或多項目間的需要，在項目執(zhí)行過程中人員被借用來或抽調走的情況非常普遍；對于機械設備等資源，在不同的項目間被來回占用的情況更是常見。這種資源量隨時間變動的項目調度問題是標準RCPSP的一個擴展和補充，它更符合許多項目資源配置的實際情況。Klein[1]采用禁忌搜索算法求解了資源量變動需求固定的RCPSP問題。Hartmann[2]描述了一個真實醫(yī)療科研項目，項目中每個活動僅在活動執(zhí)行的最后時期需要醫(yī)療設備，且研究人員和實驗設備這兩種資源量是變動的。
RCPSP在組合優(yōu)化中屬于NP-hard問題，其求解方法分為精確算法和啟發(fā)式算法兩大類。由于啟發(fā)式算法與精確算法相比，操作簡便靈活，易于移植，同時近年來先進進化算法和智能算法不斷涌現(xiàn)，應用與智能算法相結合的啟發(fā)式算法來求解RCPSP受到更多學者的青睞。2005年，Karaboga[3]提出了一種人工蜂群算法ABC(Artificial Bee Colony)，用以解決連續(xù)型多峰函數(shù)尋優(yōu)問題。Akbari[4]等用ABC算法求解了基于優(yōu)先權的標準RCPSP。不足之處在于，ABC算法針對連續(xù)性優(yōu)化問題提出，參考文獻[4]在求解RCPSP時也是按連續(xù)型問題進行處理的，沒有考慮解的離散性特點。
本文在研究資源量隨時間變動的RCPSP解的特點的基礎上，提出了一種基于任務排列的離散的食物源編碼方法，進而通過離散人工蜂群算法DABC（Discrete Artificial Bee Colony）求解項目的優(yōu)化調度方案。
1 問題描述
資源時變的RCPSP可描述如下：設項目的任務集為J={0,1,2,…,n,n+1}，任務工時已知且任務不可拆分，任務0和任務n+1為虛任務，工期為0,分別代表開始任務和結束任務。sj、fj、dj分別表示第j項任務的開始時間、結束時間和總耗時，其中sj=fj-dj。每項任務必須在其所有的緊前任務完成后方能開始，Pj為任務j的緊前任務集合。設項目共有K種可更新資源，每種可用資源的最大限額隨項目執(zhí)行的時間而變化，則第k種資源在t時刻的最大可用限額為Rkt，t為項目執(zhí)行中的每一時刻（t=1，2，…，T），T為項目工期。每個任務對資源的需求量為常量，第j項任務對第k種資源的需求量為rjk。A(t)代表t時刻正在執(zhí)行的任務的集合。項目調度的優(yōu)化目標是項目工期最短，則建立該問題的數(shù)學模型為：
2 人工蜂群算法的基本原理
ABC算法是一種模擬自然蜜蜂覓食中群體智能行為的元啟發(fā)算法。該算法中人工蜂群包含三類蜂[3]：工作蜂、跟隨蜂和偵察蜂。蜂群按數(shù)量等分成兩組，前一半是工作蜂，后一半是跟隨蜂，另設一個偵察蜂。工作蜂在蜜源采蜜,并將蜜源信息帶回，在蜂巢跳舞場以“擺尾舞”的方式與跟隨蜂分享信息，其舞蹈形態(tài)與蜜源的蜂蜜量成正比。跟隨蜂通過觀察工作蜂的舞蹈獲得蜜源信息，然后依據(jù)蜜源的蜂蜜量選擇一個適當?shù)氖澄镌?，好蜜源將會吸引更多的跟隨蜂去采蜜。當一個蜜源被多次采蜜后就會被拋棄，然后由偵察蜂去勘探一個新蜜源。蜂群中每一個工作蜂對應一個食物源，即蜜源，每個食物源的位置代表優(yōu)化問題的一個可行解，食物源的蜂蜜量稱為適應值，適應值的大小表征相關解的質量。適應值越大，蜂蜜量越多，解的質量越好。ABC算法的簡明步驟如下：
(1)人工蜂群的初始化
(2)迭代
①將人工蜂放置到食物源采蜜；
②將跟隨蜂放置到食物源采蜜；
③派偵察蜂尋找新的食物源；
④更新目前為止找到的最好食物源。
(3)停止(滿足迭代停止條件)
工作蜂有SN個，xi是一個D維向量，代表工作蜂i對應的食物源。每次迭代工作蜂i在原食物源xi的基礎上再生成候選食物源vi，候選食物源vi由下式生成：
初始食物源的位置需要通過調度生成機制產生可行調度方案。本文采用改進的串行調度生成機制來生成初始食物源。改進的串行調度包含l=1，2，…，n個階段，每個階段在先序任務已處理完的待處理任務集合中隨機地選擇一個任務并安排其執(zhí)行時間，任務安排遵循在滿足隨時間變動的資源限制的條件下開始時間越早越好的原則。
3.2 候選食物源的生成
ABC算法中候選食物源的生成方式是優(yōu)化效果和效率好壞的關鍵。本文基于任務排列的食物源位置編碼對應了項目調度方案，生成候選食物源時既要保持食物源編碼的離散性又要保持食物源編碼對應的調度方案的可行性，為此本文采用了一種新的候選食物源生成方法。
仍以圖1所示項目為例來說明候選食物源的生成方法，設食物源xi=(1，2，4，5，3，6)，選定的相鄰食物源xk=(1，3，2，4，5，6)，隨機生成一位d=3。則候選食物源vi的生成方法為：vi的前兩個元素取xi的前兩個元素(1，2)，去除xk中與xi的前兩個元素相同的元素即得(3，4，5，6)，取該矩陣中第一個元素為vi的第三個元素，則vi的前三個元素取為(1，2，3)，再從xi中去除(1，2，3)得到(4，5，6)作為vi的后三個元素。這樣得到vi=(1，2，
3，4，5，6)?？梢宰C明，采用這種方法得到的候選食物源滿足項目任務的先序關系，是可行調度[5]。
3.3 適應值函數(shù)
DABC算法中食物源位置編碼唯一對應了一種項目調度的任務排列方案，由這一方案可進一步得到任務的時間安排。時間安排也是在串行調度基礎上，遵循在滿足隨時間變動的資源限制的條件下，開始時間越早越好的原則。這樣就得到了該食物源對應的任務時間安排和項目工期。資源時變的RCPSP的優(yōu)化目標是項目工期最短，工期越短意味著調度方案越好，也就意味著該方案所對應的食物源蜂蜜量越多，適應值越大。因此ABC算法中食物源xi的適應值fiti可由式(4)得到：
3.4 DABC算法的基本框架
基于上述原理，求解資源時變的RCPSP的DABC算法實現(xiàn)的基本框架如圖3所示。
4 算例仿真
為了驗證DABC算法求解資源隨時間變動的RCPSP的有效性，本文選取了一個有27個任務的項目算例[6]。如圖4所示，任務0和任務26為虛任務，項目的可更新資源種類為3種，圖中結點圓圈內數(shù)字為任務編號，結點上方數(shù)字為任務工期，結點下方數(shù)字分別為該任務對3種資源的使用量。
4.1 DABC求解標準RCPSP
設圖4項目的三種資源在單位時間內最大使用限額在整個項目執(zhí)行期間固定不變，均取為6[6]。首先對這一標準RCPSP問題進行驗證計算。本文用ABC與DABC兩種算法進行計算，圖5給出了在10次仿真實驗中平均優(yōu)化過程，算法中蜂群數(shù)量NP=30，即食物源SN=15，最大迭代次數(shù)Cmax=200，trailmax=3。另外，ABC算法工作蜂生成候選食物源應用式(2)時取參數(shù)1=2，跟隨蜂尋找候選食物源應用式(2)時，取參數(shù)?棕2=3。兩種算法得到的項目工期的最優(yōu)解均為64天，同時在最優(yōu)工期下可以得到多種最優(yōu)調度方案。優(yōu)化結果與參考文獻[6]一致。由圖5可以看出DABC算法能很好地保持種群的多樣性，優(yōu)化效果要好于ABC算法，同時運算速度也要比ABC算法快。
由DABC算法得到在項目工期為64時最優(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]，此時三種資源的利用情況如圖6所示。
得到滿足。
4.3 結果分析
章節(jié)4.1和章節(jié)4.2的計算是對同一項目在不同資源配置情況下得到的優(yōu)化調度方案。前者中項目三種資源的總可用量為[384,384,384]，后者中項目三種資源的總可用量為[345,326,321]。從資源配置來看，前者中各種資源可用總量都要比后者的大，但是后者資源配置方法卻使得項目工期縮短了整整20天，比前者完工期提前了31.25%。
由此可知，在資源總量保持不變甚至減少的情況下，通過調整資源在項目執(zhí)行期間的配置情況，可以有效地縮短項目工期。這種調整資源配置的方法在實際項目的運作中無疑是可以操作和實現(xiàn)的。
本文采用一種新的離散人工蜂群算法對資源隨時間變化的受限項目調度優(yōu)化問題進行研究，這一問題是對標準RCPSP的必要補充和擴展。通過實例仿真可以得到如下結論：第一，本文所提出的DABC算法能有效地求解資源量隨時間變動的RCPSP和標準RCPSP，比ABC算法有更好的收斂特性；第二，資源時變的RCPSP更符合項目實際，通過調整資源在項目執(zhí)行中的配置情況，可以在保持可用資源總量不變或減少的情況下顯著地縮短項目工期，提高資源利用率。這一結論在今后項目管理中應給予充分的重視。
參考文獻
[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.