摘  要： 針對資源受限項目調(diào)度問題，提出了一種基于人工蜂群算法的優(yōu)化方法。人工蜂群算法中每個食物源的位置代表一種項目任務(wù)的優(yōu)先權(quán)序列，每個食物源的位置通過擴展串行調(diào)度機制轉(zhuǎn)換成可行的調(diào)度方案，迭代中由三種人工蜂執(zhí)行不同的操作來實現(xiàn)全局最優(yōu)解的更新。實驗結(jié)果表明，人工蜂群算法是求解資源受限項目調(diào)度問題的有效方法，同時擴展調(diào)度機制的引入可以加速迭代收斂的進程。
關(guān)鍵詞： 資源受限項目調(diào)度；人工蜂群算法；擴展串行調(diào)度

　現(xiàn)代項目管理的理念和方法已經(jīng)被越來越多的組織所接受，成為組織模式中不可或缺的一部分，而項目調(diào)度是項目管理中最具挑戰(zhàn)行性的工作。由于項目的可用資源稀缺及項目任務(wù)間的必須滿足的工序關(guān)系，使得項目調(diào)度成為一個十分復(fù)雜的問題。資源受限的項目調(diào)度RCPSP(Resource-Constrained Project Scheduling)問題是一類典型的組合優(yōu)化問題，在理論上Blazewicz[1]已經(jīng)證明它屬于強NP-hard問題，對于大規(guī)模的項目調(diào)度采用精確解法求解就變得十分困難，而啟發(fā)式算法在求解速度上則表現(xiàn)出明顯的優(yōu)越性。近年來國內(nèi)外學(xué)者對基于優(yōu)先規(guī)則的啟發(fā)式算法做了大量的研究，先進進化和智能算法不斷出現(xiàn)(如模擬退火算法、禁忌搜索算法、遺傳算法，及蟻群算法、粒子群算法等)，并被逐步應(yīng)用到RCPSP問題求解中。
受到蜜蜂群體采蜜行為的啟發(fā)，2005年Karaboga[2]提出了一種基于蜂群智能的新的人工蜂群算法ABC(Artificial Bee Colony)。Karaboga等[3-4]已經(jīng)驗證與遺傳算法、差分進化算法及粒子群算法相比，ABC算法在連續(xù)型多峰函數(shù)尋優(yōu)問題中能得到更好的結(jié)果。ABC算法是連續(xù)性問題優(yōu)化提出的，在離散性問題，如組合優(yōu)化等問題中的應(yīng)用還比較少。
本文根據(jù)資源受限項目調(diào)度問題的解的特點，提出了一種基于優(yōu)先權(quán)的求解RCPSP的人工蜂群算法，并通過實例仿真驗證了算法的有效性。
1 問題描述
　典型的資源受限項目調(diào)度問題基于下述假設(shè)：(1)組成項目的各任務(wù)是確定的，且工期已知；(2)每項任務(wù)必須在其所有的緊前任務(wù)完成后方能開始；(3)項目的可用資源為多種可更新資源，已知資源可用量的最大限額且在項目整個過程中保持不變；(4)任務(wù)不可拆分，即任務(wù)一旦開始不得中斷；(5)調(diào)度的優(yōu)化目標是項目工期最短。因此，RCPSP可描述為：設(shè)項目的任務(wù)集為J={0，1，2，…，n，n+1}，其中任務(wù)0和n+1為虛任務(wù)，工期為0，分別代表開始任務(wù)和結(jié)束任務(wù)。sj=fj-dj，C={(i，j)|i必須在j開始前完成}為項目的緊前任務(wù)集，其中sj、fj、dj分別表示第j項任務(wù)的開始時間、結(jié)束時間和總耗時。設(shè)項目共有K種可更新資源，第k種資源的總量為Rk，第j項任務(wù)對第k種資源的需求量為rjk。則資源受限的項目調(diào)度的數(shù)學(xué)模型為：

2 人工蜂群算法求解RCPSP
2.1 人工蜂群算法簡介
　人工蜂群算法是一種基于群智能的元啟發(fā)算法，因其原理簡單易于實現(xiàn)的特點受到了越來越多的關(guān)注。人工蜂群算法中有兩個重要組成：人工蜜蜂和食物源。人工蜜蜂分為三類：工作蜂、跟隨蜂和偵查蜂，每一種人工蜂扮演不同的角色。工作蜂在蜜源采蜜，并將蜜源信息帶回與跟隨蜂分享；跟隨蜂等候在蜂巢從回來的工作蜂那里得到食物源的信息；偵查蜂負責(zé)尋找新蜜源。工作蜂通過在蜂巢跳舞場以“擺尾舞”的方式分享信息，其舞蹈形態(tài)和采蜜蜜源的蜂蜜量成正比。跟隨蜂觀察舞蹈，然后依據(jù)分享蜜源的蜂蜜量選擇適當(dāng)?shù)氖澄镌?，好蜜源將會吸引更多的跟隨蜂。當(dāng)一個蜜源被多次采蜜后，就會被拋棄，然后偵查蜂就會勘探另一個新蜜源。因此，偵查蜂的作用可以看做是開發(fā)食物源，而工作蜂和跟隨蜂的作用是開采食物源。蜂群按數(shù)量等分成兩組，前一半是工作蜂，后一半是跟隨蜂。每一個工作蜂對應(yīng)一個食物源，即工作蜂的數(shù)目和蜂巢周圍的食物源的數(shù)目相等。在ABC算法中食物源即蜜源，每個食物源的位置代表優(yōu)化問題的一個可行解，食物源的蜂蜜量稱為適應(yīng)值，代表相關(guān)解的質(zhì)量。
2.2 人工蜂群算法求解RCPSP
　本文ABC算法的基礎(chǔ)采用基于優(yōu)先權(quán)編碼的人工蜂群算法對RCPSP進行求解。
2.2.1 基于優(yōu)先權(quán)的食物源位置編碼
　在ABC算法中，每個食物源的位置代表一個可行解。在用ABC算法求解資源受限項目調(diào)度問題時，每個食物源的位置xi是一個n維向量，取xi=(xi1，xi2，…，xid，…，xin)，向量的維數(shù)n即是項目的非虛擬任務(wù)數(shù)。食物源xi代表一種項目任務(wù)的優(yōu)先權(quán)序列。其中，xid是第i個食物源的第d個位置的值，它對應(yīng)了第d項任務(wù)的優(yōu)先權(quán)為xid。ABC算法得到的xi是連續(xù)數(shù)構(gòu)成的向量，通過把xi向量元素按從小到大排序，轉(zhuǎn)換成1~n的整數(shù)排列。這種整數(shù)優(yōu)先權(quán)序列再通過調(diào)度生成機制轉(zhuǎn)換為一個可行的調(diào)度方案。
2.2.2 適應(yīng)值函數(shù)
　ABC算法中食物源的好壞用蜂蜜量的多少來衡量，蜂蜜量是指食物源對應(yīng)的可行解的適應(yīng)值函數(shù)。在RCPSP中食物源對應(yīng)了項目任務(wù)的優(yōu)先權(quán)序列，優(yōu)先權(quán)序列可以通過調(diào)度生成機制轉(zhuǎn)換成可行調(diào)度方案，每一調(diào)度方案對應(yīng)了項目工期。RCPSP優(yōu)化目標是使項目工期最短，并意味著解的質(zhì)量越好，因此ABC算法中食物源xi的適應(yīng)值fiti?？捎墒?4)轉(zhuǎn)換得到。

2.2.3 擴展串行調(diào)度生成機制
　一個食物源的位置編碼對應(yīng)了項目的一種任務(wù)優(yōu)先權(quán)序列，需要通過適當(dāng)?shù)恼{(diào)度生成機制把任務(wù)的優(yōu)先權(quán)轉(zhuǎn)化為可行的調(diào)度方案，本文采用擴展的串行調(diào)度生成機制[5]來生成可行調(diào)度方案。串行調(diào)度有兩種對齊調(diào)度方式，一種是左齊計劃，一種是右齊計劃。所謂擴展的串行調(diào)度機制就是采用雙齊計劃進行調(diào)度，實現(xiàn)過程分為：(1)采用串行調(diào)度方法生成一個左齊計劃；(2)在左齊計劃的基礎(chǔ)上，以左齊計劃的結(jié)束任務(wù)完工時間為基準，再生成右齊計劃；(3)若右齊計劃開始任務(wù)開始時間大于零，則整個右齊計劃同步左移至開始任務(wù)最早開始時間為零，即再進行一個左齊計劃。通過這一調(diào)度機制就可以實現(xiàn)將食物源的解轉(zhuǎn)換為可行的調(diào)度方案。
2.2.4 算法的實現(xiàn)步驟
　ABC算法求解RCPSP的實現(xiàn)步驟如下：
　(1)初始化。ABC算法首先產(chǎn)生初始種群，種群數(shù)量為SN，也代表SN個解(食物源)。每一個解xi(i=1，2，…，SN)對應(yīng)了一組任務(wù)優(yōu)先權(quán)序列，通過擴展的串行調(diào)度生成機制得到可行的調(diào)度方案，計算出每個xi的適應(yīng)值fiti。
　(2)迭代過程。在初始化之后，進入迭代(C=1，2，…，Cmax)過程，Cmax為最大迭代次數(shù)。在每次迭代中，三種類型的人工蜂執(zhí)行不同的操作，種群的全局最優(yōu)解就隨著人工蜂群每次迭代中所尋找的食物源適應(yīng)值的情況不斷更新。
?、俟ぷ鞣溆蠸N個，對應(yīng)SN個食物源，工作蜂i的食物源為xi，工作蜂i在種群中隨機選擇一個工作蜂k做它的鄰居，并在工作蜂k的食物源xk的n維向量中隨機選擇一位d(d=1，2，…，n)。vi為工作蜂i的候選食物源，vi與xi除了第j位vid外，其余各位和xi一致。vid的計算方法為：

　其中，fiti為工作蜂i的食物源的適應(yīng)值。跟隨蜂j通過輪盤賭的形式從工作蜂的食物源中選擇食物源，假設(shè)工作蜂i的食物源xi被選中，跟隨蜂j采用和①相同的方法來生產(chǎn)侯選食物源vi，同時采用和①相同貪婪策略在vi和xi之間進行取舍，traili的設(shè)置方法亦同上。
　③當(dāng)某一食物源xi的traili等于最大重復(fù)使用次數(shù)的限定值時，偵查蜂就會隨機生成一個新的食物源取代xi，原來的食物源被舍棄不用。
　(3)結(jié)束。當(dāng)步驟(2)完成Cmax次迭代后，ABC算法結(jié)束，輸出最優(yōu)調(diào)度方案及項目最短工期。
3 仿真實驗
　為了驗證ABC算法求解RCPSP的有效性，本文選取的算例為項目的結(jié)點式網(wǎng)絡(luò)圖[6]，如圖1所示，項目的任務(wù)集為J={0，1，2，…，25，26}，任務(wù)0和26為虛任務(wù)。項目的可更新資源種類為三種，每種資源在單位時間內(nèi)大最大使用限額為6。圖1中，結(jié)點圓圈內(nèi)數(shù)字為任務(wù)編號，結(jié)點上方數(shù)字為任務(wù)工期，結(jié)點下方數(shù)字分別為該任務(wù)對三種資源的使用量。

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

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

　本文針對資源受限的項目調(diào)度優(yōu)化問題的數(shù)學(xué)模型，提出了一種基于優(yōu)先權(quán)編碼的人工蜂群算法，通過擴展的串行調(diào)度生成機制將優(yōu)先權(quán)編碼轉(zhuǎn)換為可行的調(diào)度方案。實際算例仿真結(jié)果表明，人工蜂群算法能夠有效地求解資源受限的項目調(diào)度問題，算法的收斂速度較快，精度較高。既提高了算法的優(yōu)化效率，又提高了算法的優(yōu)化精度，同時擴展調(diào)度機制與串行調(diào)度生成機制相比具有明顯的優(yōu)點。
參考文獻
[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. On the performance of artificial bee colony(ABC) algorithm[J]. Applied Soft Computing. 2008，8(1)：687-697.
[5] Deng Linyi， Lin Yan， Chen Ming. Hybrid ant colony optimization for the resource-constrained project scheduling problem[J]. Journal of Systems Engineering and Electronics 2010，21(1)：67-71.
[6] Zhang Hong， Li Heng， TAM C M. Particle swarm optimization for resource-constrained project scheduling[J]. International Journal of Project Management 2006，24：83-92.