離散人工蜂群算法求解資源時變的項目調度問題

孫曉雅，王金羽

（遼寧師范大學 管理學院，遼寧 大連116029）

自上世紀60年代以來，資源受限項目調度問題RCPSP(Resource-Constrained Project Scheduling)引起了國內外學者的極大關注，RCPSP是指在滿足資源約束和任務先序關系條件下，合理安排調度，以實現項目的既定目標最優（通常為項目工期最短）。目前，標準RCPSP已經成為運籌學領域的一個經典問題，它建立在一定假設之上，如假定項目的可用資源均為可更新資源，資源的最大可用量在整個項目執行期間已知且保持不變。而實際項目中可用資源量卻經常是隨時間變化的。以人力資源為例，由于組織或多項目間的需要，在項目執行過程中人員被借用來或抽調走的情況非常普遍；對于機械設備等資源，在不同的項目間被來回占用的情況更是常見。這種資源量隨時間變動的項目調度問題是標準RCPSP的一個擴展和補充，它更符合許多項目資源配置的實際情況。Klein[1]采用禁忌搜索算法求解了資源量變動需求固定的RCPSP問題。Hartmann[2]描述了一個真實醫療科研項目，項目中每個活動僅在活動執行的最后時期需要醫療設備，且研究人員和實驗設備這兩種資源量是變動的。

RCPSP在組合優化中屬于NP-hard問題，其求解方法分為精確算法和啟發式算法兩大類。由于啟發式算法與精確算法相比，操作簡便靈活，易于移植，同時近年來先進進化算法和智能算法不斷涌現，應用與智能算法相結合的啟發式算法來求解RCPSP受到更多學者的青睞。2005年，Karaboga[3]提出了一種人工蜂群算法 ABC(Artificial Bee Colony)，用以解決連續型多峰函數尋優問題。Akbari[4]等用ABC算法求解了基于優先權的標準RCPSP。不足之處在于，ABC算法針對連續性優化問題提出，參考文獻[4]在求解RCPSP時也是按連續型問題進行處理的，沒有考慮解的離散性特點。

本文在研究資源量隨時間變動的RCPSP解的特點的基礎上，提出了一種基于任務排列的離散的食物源編碼方法，進而通過離散人工蜂群算法DABC（Discrete Artificial Bee Colony）求解項目的優化調度方案。

1 問題描述

資源時變的RCPSP可描述如下：設項目的任務集為J={0,1,2,…,n,n+1}，任務工時已知且任務不可拆分，任務0和任務n+1為虛任務，工期為0,分別代表開始任務和結束任務。sj、fj、dj分別表示第 j項任務的開始時間、結束時間和總耗時，其中sj=fj-dj。每項任務必須在其所有的緊前任務完成后方能開始，Pj為任務j的緊前任務集合。設項目共有K種可更新資源，每種可用資源的最大限額隨項目執行的時間而變化，則第k種資源在t時刻的最大可用限額為 Rkt，t為項目執行中的每一時刻（t=1，2，…，T），T為項目工期。 每個任務對資源的需求量為常量，第j項任務對第k種資源的需求量為rjk。A(t)代表t時刻正在執行的任務的集合。項目調度的優化目標是項目工期最短，則建立該問題的數學模型為：

2 人工蜂群算法的基本原理

ABC算法是一種模擬自然蜜蜂覓食中群體智能行為的元啟發算法。該算法中人工蜂群包含三類蜂[3]：工作蜂、跟隨蜂和偵察蜂。蜂群按數量等分成兩組，前一半是工作蜂，后一半是跟隨蜂，另設一個偵察蜂。工作蜂在蜜源采蜜,并將蜜源信息帶回，在蜂巢跳舞場以“擺尾舞”的方式與跟隨蜂分享信息，其舞蹈形態與蜜源的蜂蜜量成正比。跟隨蜂通過觀察工作蜂的舞蹈獲得蜜源信息，然后依據蜜源的蜂蜜量選擇一個適當的食物源，好蜜源將會吸引更多的跟隨蜂去采蜜。當一個蜜源被多次采蜜后就會被拋棄，然后由偵察蜂去勘探一個新蜜源。蜂群中每一個工作蜂對應一個食物源，即蜜源，每個食物源的位置代表優化問題的一個可行解，食物源的蜂蜜量稱為適應值，適應值的大小表征相關解的質量。適應值越大，蜂蜜量越多，解的質量越好。ABC算法的簡明步驟如下：

(1)人工蜂群的初始化

(2)迭代

①將人工蜂放置到食物源采蜜；

②將跟隨蜂放置到食物源采蜜；

③派偵察蜂尋找新的食物源；

④更新目前為止找到的最好食物源。

(3)停止(滿足迭代停止條件)

工作蜂有SN個，xi是一個D維向量，代表工作蜂i對應的食物源。每次迭代工作蜂i在原食物源xi的基礎上再生成候選食物源vi，候選食物源vi由下式生成：

其中，xk為工作蜂i隨機選擇的相鄰工作蜂k對應的食物源，xid是食物源 xi的第 d位，xkd是相鄰食物源 xk的第d位，φid是[-1，1]上的隨機數，ω是控制當前食物源和相鄰食物源差別大小的參數。候選食物源vi與xi除了第d位vid外，其余各位與 xi一致。vid的計算方法如式(2)所示。vi生成后，vi和xi之間通過貪婪策略進行選擇。

跟隨蜂也有SN個，跟隨蜂j通過輪盤賭的形式從工作蜂的食物源中選擇食物源，輪盤賭中工作蜂的食物源的蜂蜜量的概率值pi的計算如式(3)所示。

其中，fiti為工作蜂i的食物源的適應值。假設工作蜂i的食物源xi被選中，跟隨蜂j采用與工作蜂相同的方法來生成候選食物源。

3 離散人工蜂群算法求解資源時變的RCPSP

3.1 基于任務排列的食物源位置編碼

考慮到RCPSP的解的特點，本文所述DABC算法采用基于任務排列的食物源位置編碼方法。每個食物源的位置 xi=(xi1，xi2，…，xid，…，xin)是非虛擬任務{1，2，…，n}的一種排列，同時它又滿足所有任務的緊前關系。每個xi都唯一對應了一種可行的項目調度方案。

以一個6個實任務的項目為例，單代號網絡圖如圖1所示，該項目有一種可用資源，最大資源量為4。若食物源編碼為 xi=(1，2，4，5，3，6)，該食物源編碼所對應的項目調度方案如圖2所示，此時項目工期為16。

初始食物源的位置需要通過調度生成機制產生可行調度方案。本文采用改進的串行調度生成機制來生成初始食物源。改進的串行調度包含l=1，2，…，n個階段，每個階段在先序任務已處理完的待處理任務集合中隨機地選擇一個任務并安排其執行時間，任務安排遵循在滿足隨時間變動的資源限制的條件下開始時間越早越好的原則。

3.2 候選食物源的生成

ABC算法中候選食物源的生成方式是優化效果和效率好壞的關鍵。本文基于任務排列的食物源位置編碼對應了項目調度方案，生成候選食物源時既要保持食物源編碼的離散性又要保持食物源編碼對應的調度方案的可行性，為此本文采用了一種新的候選食物源生成方法。

仍以圖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)。可以證明，采用這種方法得到的候選食物源滿足項目任務的先序關系，是可行調度[5]。

3.3 適應值函數

DABC算法中食物源位置編碼唯一對應了一種項目調度的任務排列方案，由這一方案可進一步得到任務的時間安排。時間安排也是在串行調度基礎上，遵循在滿足隨時間變動的資源限制的條件下，開始時間越早越好的原則。這樣就得到了該食物源對應的任務時間安排和項目工期。資源時變的RCPSP的優化目標是項目工期最短，工期越短意味著調度方案越好，也就意味著該方案所對應的食物源蜂蜜量越多，適應值越大。因此ABC算法中食物源xi的適應值fiti可由式(4)得到：

3.4 DABC算法的基本框架

基于上述原理，求解資源時變的RCPSP的DABC算法實現的基本框架如圖3所示。

4 算例仿真

為了驗證DABC算法求解資源隨時間變動的RCPSP的有效性，本文選取了一個有27個任務的項目算例[6]。如圖4所示，任務0和任務26為虛任務，項目的可更新資源種類為3種，圖中結點圓圈內數字為任務編號，結點上方數字為任務工期，結點下方數字分別為該任務對3種資源的使用量。

4.1 DABC求解標準RCPSP

圖3 求解資源時變RCPSP的DABC算法流程圖

圖5 ABC算法與DABC算法的優化過程對比

設圖4項目的三種資源在單位時間內最大使用限額在整個項目執行期間固定不變，均取為6[6]。首先對這一標準RCPSP問題進行驗證計算。本文用ABC與DABC兩種算法進行計算，圖5給出了在10次仿真實驗中平均優化過程，算法中蜂群數量NP=30，即食物源SN=15，最大迭代次數 Cmax=200，trailmax=3。另外，ABC算法工作蜂生成候選食物源應用式(2)時取參數ω1=2，跟隨蜂尋找候選食物源應用式(2)時，取參數ω2=3。兩種算法得到的項目工期的最優解均為64天，同時在最優工期下可以得到多種最優調度方案。優化結果與參考文獻[6]一致。由圖5可以看出DABC算法能很好地保持種群的多樣性，優化效果要好于ABC算法，同時運算速度也要比ABC算法快。

由DABC算法得到在項目工期為64時最優食物源編碼為[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.2 DABC求解資源時變的RCPSP

對圖4所示項目，設三種資源的可用量在項目執行期間發生變化，變化情況事先已知，如表1所示。

表1 項目三種資源的可用量隨時間的變化情況

對上述資源時變項目用DABC算法進行求解，得到項目最短工期為44天，此時基于任務排列的最優食物源編碼為[1,2,4,3,9,7,5,6,14,8,17,13,11,10,15,12,18,19,22,16,20,23,21,24,25]。圖7為最優調度時資源的使用情況，其中階梯狀折線表示三種資源在項目執行中可用資源量的最大限額，可見最優調度時三種資源的限制均得到滿足。

4.3 結果分析

章節4.1和章節4.2的計算是對同一項目在不同資源配置情況下得到的優化調度方案。前者中項目三種資源的總可用量為[384,384,384]，后者中項目三種資源的總可用量為[345,326,321]。從資源配置來看，前者中各種資源可用總量都要比后者的大，但是后者資源配置方法卻使得項目工期縮短了整整20天，比前者完工期提前了31.25%。

由此可知，在資源總量保持不變甚至減少的情況下，通過調整資源在項目執行期間的配置情況，可以有效地縮短項目工期。這種調整資源配置的方法在實際項目的運作中無疑是可以操作和實現的。

本文采用一種新的離散人工蜂群算法對資源隨時間變化的受限項目調度優化問題進行研究，這一問題是對標準RCPSP的必要補充和擴展。通過實例仿真可以得到如下結論：第一，本文所提出的DABC算法能有效地求解資源量隨時間變動的RCPSP和標準RCPSP，比ABC算法有更好的收斂特性；第二，資源時變的RCPSP更符合項目實際，通過調整資源在項目執行中的配置情況，可以在保持可用資源總量不變或減少的情況下顯著地縮短項目工期，提高資源利用率。這一結論在今后項目管理中應給予充分的重視。

[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.