人工蜂群算法求解資源受限項目調度問題

孫曉雅

(遼寧師范大學 管理學院，遼寧 大連 116029)

現代項目管理的理念和方法已經被越來越多的組織所接受，成為組織模式中不可或缺的一部分，而項目調度是項目管理中最具挑戰行性的工作。由于項目的可用資源稀缺及項目任務間的必須滿足的工序關系，使得項目調度成為一個十分復雜的問題。資源受限的項目調度RCPSP(Resource-Constrained Project Scheduling)問題是一類典型的組合優化問題，在理論上Blazewicz[1]已經證明它屬于強NP-hard問題，對于大規模的項目調度采用精確解法求解就變得十分困難，而啟發式算法在求解速度上則表現出明顯的優越性。近年來國內外學者對基于優先規則的啟發式算法做了大量的研究，先進進化和智能算法不斷出現(如模擬退火算法、禁忌搜索算法、遺傳算法，及蟻群算法、粒子群算法等)，并被逐步應用到RCPSP問題求解中。

受到蜜蜂群體采蜜行為的啟發，2005年Karaboga[2]提出了一種基于蜂群智能的新的人工蜂群算法ABC(Artificial Bee Colony)。Karaboga等[3-4]已經驗證與遺傳算法、差分進化算法及粒子群算法相比，ABC算法在連續型多峰函數尋優問題中能得到更好的結果。ABC算法是連續性問題優化提出的，在離散性問題，如組合優化等問題中的應用還比較少。

本文根據資源受限項目調度問題的解的特點，提出了一種基于優先權的求解RCPSP的人工蜂群算法，并通過實例仿真驗證了算法的有效性。

1 問題描述

典型的資源受限項目調度問題基于下述假設：(1)組成項目的各任務是確定的，且工期已知；(2)每項任務必須在其所有的緊前任務完成后方能開始；(3)項目的可用資源為多種可更新資源，已知資源可用量的最大限額且在項目整個過程中保持不變；(4)任務不可拆分，即任務一旦開始不得中斷；(5)調度的優化目標是項目工期最短。因此，RCPSP可描述為：設項目的任務集為J={0，1，2，…，n，n+1}，其中任務 0 和 n+1 為虛任務，工期為0，分別代表開始任務和結束任務。sj=fj-dj，C={(i，j)|i必須在 j開始前完成}為項目的緊前任務集，其中 sj、fj、dj分別表示第j項任務的開始時間、結束時間和總耗時。設項目共有K種可更新資源，第k種資源的總量為Rk，第j項任務對第k種資源的需求量為rjk。則資源受限的項目調度的數學模型為：

式中，T為項目工期，t為項目執行中的每一時刻(t=1，2，…，T)。A(t)為 t時刻正在執行的任務的集合。

在上述模型中，式(1)為目標函數優化目標，是項目最短的完工工期。式(2)、(3)為約束條件，式(2)表示滿足任務間的緊前關系及任務工時要求；式(3)表示在項目執行中任一時刻必須滿足各種資源限制。

2 人工蜂群算法求解RCPSP

2.1 人工蜂群算法簡介

人工蜂群算法是一種基于群智能的元啟發算法，因其原理簡單易于實現的特點受到了越來越多的關注。人工蜂群算法中有兩個重要組成：人工蜜蜂和食物源。人工蜜蜂分為三類：工作蜂、跟隨蜂和偵查蜂，每一種人工蜂扮演不同的角色。工作蜂在蜜源采蜜，并將蜜源信息帶回與跟隨蜂分享；跟隨蜂等候在蜂巢從回來的工作蜂那里得到食物源的信息；偵查蜂負責尋找新蜜源。工作蜂通過在蜂巢跳舞場以“擺尾舞”的方式分享信息，其舞蹈形態和采蜜蜜源的蜂蜜量成正比。跟隨蜂觀察舞蹈，然后依據分享蜜源的蜂蜜量選擇適當的食物源，好蜜源將會吸引更多的跟隨蜂。當一個蜜源被多次采蜜后，就會被拋棄，然后偵查蜂就會勘探另一個新蜜源。因此，偵查蜂的作用可以看做是開發食物源，而工作蜂和跟隨蜂的作用是開采食物源。蜂群按數量等分成兩組，前一半是工作蜂，后一半是跟隨蜂。每一個工作蜂對應一個食物源，即工作蜂的數目和蜂巢周圍的食物源的數目相等。在ABC算法中食物源即蜜源，每個食物源的位置代表優化問題的一個可行解，食物源的蜂蜜量稱為適應值，代表相關解的質量。

2.2 人工蜂群算法求解RCPSP

本文ABC算法的基礎采用基于優先權編碼的人工蜂群算法對RCPSP進行求解。

2.2.1 基于優先權的食物源位置編碼

在ABC算法中，每個食物源的位置代表一個可行解。在用ABC算法求解資源受限項目調度問題時，每個食物源的位置 xi是一個 n維向量，取 xi=(xi1，xi2，…，xid，…，xin)，向量的維數n即是項目的非虛擬任務數。食物源xi代表一種項目任務的優先權序列。其中，xid是第i個食物源的第d個位置的值，它對應了第d項任務的優先權為xid。ABC算法得到的xi是連續數構成的向量，通過把xi向量元素按從小到大排序，轉換成1~n的整數排列。這種整數優先權序列再通過調度生成機制轉換為一個可行的調度方案。

2.2.2 適應值函數

ABC算法中食物源的好壞用蜂蜜量的多少來衡量，蜂蜜量是指食物源對應的可行解的適應值函數。在RCPSP中食物源對應了項目任務的優先權序列，優先權序列可以通過調度生成機制轉換成可行調度方案，每一調度方案對應了項目工期。RCPSP優化目標是使項目工期最短，并意味著解的質量越好，因此ABC算法中食物源xi的適應值 fiti?？捎墒?4)轉換得到。

2.2.3 擴展串行調度生成機制

一個食物源的位置編碼對應了項目的一種任務優先權序列，需要通過適當的調度生成機制把任務的優先權轉化為可行的調度方案，本文采用擴展的串行調度生成機制[5]來生成可行調度方案。串行調度有兩種對齊調度方式，一種是左齊計劃，一種是右齊計劃。所謂擴展的串行調度機制就是采用雙齊計劃進行調度，實現過程分為：(1)采用串行調度方法生成一個左齊計劃；(2)在左齊計劃的基礎上，以左齊計劃的結束任務完工時間為基準，再生成右齊計劃；(3)若右齊計劃開始任務開始時間大于零，則整個右齊計劃同步左移至開始任務最早開始時間為零，即再進行一個左齊計劃。通過這一調度機制就可以實現將食物源的解轉換為可行的調度方案。

2.2.4 算法的實現步驟

ABC算法求解RCPSP的實現步驟如下：

(1)初始化。ABC算法首先產生初始種群，種群數量為 SN，也代表 SN個解(食物源)。每一個解 xi(i=1，2，…，SN)對應了一組任務優先權序列，通過擴展的串行調度生成機制得到可行的調度方案，計算出每個xi的適應值fiti。

(2)迭代過程。在初始化之后，進入迭代(C=1，2，…，Cmax)過程，Cmax為最大迭代次數。在每次迭代中，三種類型的人工蜂執行不同的操作，種群的全局最優解就隨著人工蜂群每次迭代中所尋找的食物源適應值的情況不斷更新。

①工作蜂有SN個，對應SN個食物源，工作蜂 i的食物源為xi，工作蜂i在種群中隨機選擇一個工作蜂 k做它的鄰居，并在工作蜂k的食物源xk的n維向量中隨機選擇一位 d(d=1，2，…，n)。vi為工作蜂 i的候選食物源，vi與 xi除了第 j位 vid外，其余各位和 xi一致。vid的計算方法為：

其中，xid是食物源 xi第 d位，xkd是相鄰食物源 xk的第 d位，φid是[-1，1]上的隨機數，ω是控制當前食物源和相鄰食物源差別大小的參數。這樣，vi生成后，vi和xi之間通過貪婪策略進行選擇，即如果vi的適應值不比xi的適應值差，則xi=vi,xi重復使用的次數traili置0。否則舍棄 vi,xi保持不變，xi重復使用的次數 traili增加 1。

②跟隨蜂也有SN個，當工作蜂尋找到新的食物源后，回到蜂巢的跳舞場和跟隨蜂分享食物源的信息。工作蜂的食物源蜂蜜量的概率值pi可計算為：

其中，fiti為工作蜂i的食物源的適應值。跟隨蜂j通過輪盤賭的形式從工作蜂的食物源中選擇食物源，假設工作蜂i的食物源xi被選中，跟隨蜂j采用和①相同的方法來生產侯選食物源vi，同時采用和①相同貪婪策略在vi和xi之間進行取舍，traili的設置方法亦同上。

③當某一食物源xi的traili等于最大重復使用次數的限定值時，偵查蜂就會隨機生成一個新的食物源取代xi，原來的食物源被舍棄不用。

(3)結束。當步驟(2)完成Cmax次迭代后，ABC算法結束，輸出最優調度方案及項目最短工期。

3 仿真實驗

為了驗證ABC算法求解RCPSP的有效性，本文選取的算例為項目的結點式網絡圖[6]，如圖1所示，項目的任務集為 J={0，1，2，…，25，26}，任務 0 和 26 為虛任務。項目的可更新資源種類為三種，每種資源在單位時間內大最大使用限額為6。圖1中，結點圓圈內數字為任務編號，結點上方數字為任務工期，結點下方數字分別為該任務對三種資源的使用量。

圖1 項目的結點式網絡圖

ABC仿真實驗選取蜂群數量NP=20，即食物源SN=10，最大迭代次數Cmax=50，工作蜂生成候選食物源應用式(5)時，取參數ω1=0.7；跟隨蜂尋找候選食物源應用(5)式時，取參數ω2=1。圖2給出了ABC算法在迭代中得到的項目工期的收斂過程，項目的工期的最優解為64天，所得的最優結果與參考文獻[5]一致，同時與參考文獻[5]比較來看，由于采用了擴展的串行調度生成機制，初始解離最優解距離更近。

圖2 ABC算法求RCPSP的收斂過程

圖3給出了應用ABC算法得到的本算例最優調度時的甘特圖。圖4給出了此時項目可用資源的利用情況圖，由圖可見，在最短項目工期為64天的情況下，各任務在執行過程中滿足三種資源的限制。

圖4 最優調度時的三種資源的利用情況

本文針對資源受限的項目調度優化問題的數學模型，提出了一種基于優先權編碼的人工蜂群算法，通過擴展的串行調度生成機制將優先權編碼轉換為可行的調度方案。實際算例仿真結果表明，人工蜂群算法能夠有效地求解資源受限的項目調度問題，算法的收斂速度較快，精度較高。既提高了算法的優化效率，又提高了算法的優化精度，同時擴展調度機制與串行調度生成機制相比具有明顯的優點。

[1]BLAZEWICZ J， LENSTRA J K， RINNOOY K A H G.Scheduling subject to resource constraints：classifcation and complexity[J].Discrete Applied Mathematics.1983，5(1)：11-24.

[2]KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TRO6，2005.

[3]KARABOGA D，BASTURK B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony (ABC)algorithm[J].Journal of Global Optimization，2007，39(3)： 459-471.

[4]KARABOGA D， BASTURK， B.Ontheperformanceof artificial bee colony(ABC)algorithm[J].Applied Soft Computing.2008，8(1)：687-697.

[5]Deng Linyi， Lin Yan， Chen Ming.Hybrid antcolony optimization for the resource-constrained project scheduling problem[J].Journal of Systems Engineering and Electronics 2010，21(1)：67-71.

[6]Zhang Hong， LiHeng， TAM C M.Particle swarm optimization for resource-constrained project scheduling[J].International Journal of Project Management 2006，24：83-92.