郭琦

（上海理工大學(xué) 管理學(xué)院，中國 上海200093）

基于粒子群算法的多類資源受限項目調(diào)度

郭琦

（上海理工大學(xué) 管理學(xué)院，中國 上海200093）

隨著經(jīng)濟(jì)全球化導(dǎo)致市場競爭的日趨激烈，現(xiàn)代項目日趨復(fù)雜，要求周期更短、質(zhì)量更高、成本更低。準(zhǔn)時完工率更高，要求項目調(diào)度計劃要考慮成本、質(zhì)量、周期等綜合指標(biāo)，并具有更高的穩(wěn)定性、適應(yīng)性和準(zhǔn)確性。資源受限項目調(diào)度問題是一類典型的項目調(diào)度問題，它屬于NP-hard問題的范疇。傳統(tǒng)的項目計劃與優(yōu)化調(diào)度方法已經(jīng)無法完全滿足現(xiàn)代項目管理的實(shí)際需求。因此，在原有的項目計劃與優(yōu)化調(diào)度的基礎(chǔ)上，引入粒子群算法來更好的優(yōu)化質(zhì)量、周期和成本，最終達(dá)到最優(yōu)。本文將粒子群優(yōu)化算法應(yīng)用到資源受限調(diào)度項目問題求解中，詳細(xì)介紹了粒子群算法求解資源受限項目調(diào)度問題的求解過程。

項目調(diào)度；資源受限；粒子群算法

0 引言

資源受限項目調(diào)度問題是項目管理中最典型的問題之一，該問題模型豐富，求解困難。雖然問題本身描述非常容易，但是很難對問題求解方法進(jìn)行有效改進(jìn)。因此對項目調(diào)度問題進(jìn)行研究，具有重要的理論意義。在實(shí)踐上，目前的項目調(diào)度方法研究與現(xiàn)實(shí)調(diào)度狀況的需求依然存在著很大的差異，理論成果與實(shí)際問題之間也存在著很大的局限性，因此如何縮小理論研究與解決實(shí)際問題能力的差距，把豐富的項目調(diào)度理論成果應(yīng)用于實(shí)際生產(chǎn)調(diào)度也是研究的實(shí)際意義所在。

RCPSP問題模型豐富，且多屬于NP-hard題，求解困難。此類問題的另一特點(diǎn)是適用于某一個模型的算法，只要模型的條件稍加變化，該算法將不再適用變化后的模型。約束條件的存在也會導(dǎo)致相應(yīng)的數(shù)學(xué)模型難以建立，因此，線性規(guī)劃、動態(tài)規(guī)劃、分支定界和梯度下降等傳統(tǒng)數(shù)學(xué)方法，或是需要目標(biāo)函數(shù)的特殊信息，或是由于復(fù)雜性大導(dǎo)致優(yōu)化性能差，只能處理一般小規(guī)模的問題，難以高效高質(zhì)量地求解復(fù)雜問題。從六十年代初至今，資源受限項目調(diào)度問題已引起了大量學(xué)者的注意，現(xiàn)有對RCPSP的研究主要從兩個方面展開：一方面是從實(shí)際生活出發(fā)，為了更好的指導(dǎo)現(xiàn)實(shí)中的調(diào)度問題，將企業(yè)的實(shí)際項目特點(diǎn)納入研究范圍，如MPRCPSP（多模式資源受限項目調(diào)度問題）、DRCPSP（動態(tài)資源受限項目調(diào)度問題）等，另一方面則是研究新的求解算法來改善調(diào)度問題的優(yōu)化結(jié)果、提高求解速率，如遺傳算法、粒子群算法和蟻群算法等智能算法不斷被應(yīng)用到RCPSP中。

在經(jīng)典項目調(diào)度問題中，項目任務(wù)的工期都是確定的，或者說，采用的是傳統(tǒng)CPM方式的單一時間估計。但是，實(shí)際上很多情形下任務(wù)工期具有不確定性，其工期在一定程度上是隨機(jī)的。目前，隨機(jī)性資源受限項目調(diào)度問題 （Sochastic Resource-Constrained Project Schedule, SRCPSP）已經(jīng)成為近期項目調(diào)度研究的熱點(diǎn)。

此外，還可以在任務(wù)之間的邏輯關(guān)系、資源約束及時間約束上進(jìn)一步拓展RCPSP問題。例如，很多產(chǎn)品開發(fā)類項目是基于DSM進(jìn)行規(guī)劃的，其項目調(diào)度方式就有很大差別。作為一般緊前關(guān)系的拓展，搭接關(guān)系也增加了項目調(diào)度問題的復(fù)雜性。De Reyck&Herroelen進(jìn)一步將其拓展到多模式RCPSR[1]。Neumann&Schwindt分析了時間窗約束對項目調(diào)度的影響與應(yīng)用[2]。Chen et al.則分析了同時具有時間窗約束與時序約束下的項目調(diào)度問題[3]。目前，涉及現(xiàn)金流的資源受限項目調(diào)度問題（resource-constrained project scheduling problem with discounted cash flows,RCPSPDCF）已經(jīng)成為一個重要的研究領(lǐng)域，但由于RCPSPDCF問題的復(fù)雜性，目前尚缺乏較成功的最優(yōu)化算法，主要采用各類啟發(fā)式算法進(jìn)行求解。

由于資源受限項目調(diào)度的重要性和重大意義，所以本文采用了一種新的項目調(diào)度算法——粒子群算法 （Particle Swarm Optimization，PSO）。該算法是由Kenedy和Eberhart[4]于1995年首次提出，是一種基于群體智能的隨機(jī)啟發(fā)式優(yōu)化算法。它在許多問題中，例如：函數(shù)優(yōu)化、約束優(yōu)化、極大極小問題、多目標(biāo)優(yōu)化等均取得成功的應(yīng)用，已經(jīng)成為進(jìn)化算法的一個非常的重要分支。

粒子群算法的發(fā)展始于1995年Eberhart和 Kennedy[5]提出的基本粒子群算法。其中基本PSO的參數(shù)是固定的，在對某些函數(shù)優(yōu)化上精度較差。后來，Shi等提出了慣性因子ω遞減的改進(jìn)算法[6]，在2001年又提出了自適應(yīng)模糊調(diào)節(jié)ω的PSO，對單峰函數(shù)的處理中取得了良好的效果。Van den Bergh通過使粒子群中最佳粒子始終處于運(yùn)動狀態(tài)，得到保證收斂的局部最優(yōu)的改進(jìn)算法[7]，但其性能并不佳。Kennedy等研究了粒子群的拓?fù)浣Y(jié)構(gòu)，提出了一系列的拓?fù)浣Y(jié)構(gòu)[8]。Angeline等選擇將粒子引入到PSO中，選擇每次迭代好的粒子并復(fù)制到下一代[9]。Higashi等分別提出了自己的變異PSO算法，提高了算法的全局搜索能力，提到較高的搜索成功率[10]。Bashar等各自提出了自己的協(xié)同PSO算法，通過使用多群粒子分別優(yōu)化問題的不同維、多群粒子協(xié)同辦法來對基本算法進(jìn)得改進(jìn)嘗試[11]。Al-kazemi提出的Multi-Phase PSO在粒子群中隨機(jī)選取部分個體向全局最優(yōu)飛，而其他個體向反方向飛，以擴(kuò)大搜索空間[12]。PSO算法自提出以來，由于其計算簡單、易于實(shí)現(xiàn)、控制參數(shù)少等優(yōu)點(diǎn)，引起了國內(nèi)外相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注和研究。

1 問題描述

資源受限項目調(diào)度問題[13]（resource-constrained project scheduling problem,RCPSP）,或稱資源約束下項目調(diào)度問題，即要求在滿足項目內(nèi)部優(yōu)先關(guān)系和資源約束的前提下，合理安排項目的進(jìn)度計劃，從而優(yōu)化項目預(yù)期目標(biāo)。

資源受限項目調(diào)度問題可采用單代號方式描述為有向圖G=（V，E）；項目包含一組共J個任務(wù)，其集合記為V，第j項任務(wù)的工期為Pj；任務(wù)的開始時間記為Sj，完成時間記為Cj，假定每一項任務(wù)均不可中途暫停，因此任務(wù)的完成時間記為Cj=Sj+Pj。任務(wù)之間存在緊前關(guān)系，即有向圖G中的弧集E，如果任務(wù)j在任務(wù)h之間存在緊前關(guān)系（h，j）∈E，則任務(wù)j必須在任務(wù)h完成之后才能開始。記任務(wù)j的緊前任務(wù)集合為Pj。假設(shè)任務(wù)之間只涉及基本的緊前關(guān)系，不存在回路與反饋。項目涉及K種可更新資源，其中第k種資源的容量為Rk；第j項任務(wù)在執(zhí)行時需要若干種資源，其對第k種資源的需求量為rjk；項目在某一時刻對任一資源的需求不能超過該資源的容量。如此，則基本的RCPSP可以描述為：

2 粒子群算法

2.1 算法簡介

在粒子群算法系統(tǒng)中，每個優(yōu)化問題的潛在解都可以想象成維搜索空間上的一個點(diǎn)，稱之為“粒子”（Particle），而所有的粒子都有一個被目標(biāo)函數(shù)決定的適應(yīng)值（Fitness Value），即目標(biāo)函數(shù)值。每個粒子還有一個速度決定他們飛行的方向和距離。每一代中，粒子將跟蹤兩個最優(yōu)粒子，一是粒子本身在迄今找到的最好位置，稱為個體最好（Personal Best，pbest）位置。另一個為整個粒子群迄今為止找到的最好位置，成為全局最好位置（Global Best Position，簡稱gbest）。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。優(yōu)化搜索正是在由這樣一群隨機(jī)初始化形成的粒子而組成的一個種群中，以迭代的方式進(jìn)行的。

2.2 粒子群優(yōu)化算法的數(shù)學(xué)模型

粒子群算法一般是采用下面的公式對粒子進(jìn)行操作的[14]：

其中粒子的標(biāo)號i=1,2,…,m。t為迭代代數(shù)；ω是慣性權(quán)重因子；學(xué)習(xí)因子c1，c2。兩個正的加速度常數(shù)，一般取值為1.8；r1,r2是[0,1]之間均勻分布于的兩個隨機(jī)數(shù)。為了控制的值在合理的區(qū)域內(nèi)，需要指定Vmax和Vmin來限制。

3 多種資源受限項目調(diào)度問題求解

粒子群算法的具體步驟：

1）確定不違反緊前，緊后關(guān)系

2）確定項目活動的最早最晚開始時間

3）粒子群初始化

4）修復(fù)

在初始化后或進(jìn)化后，應(yīng)檢驗粒子是否滿足項目前后約束和開始時間約束條件，使各活動的實(shí)際開始時間滿足網(wǎng)絡(luò)計劃的前后約束關(guān)系，若不滿足，則采用修復(fù)策略，通過修復(fù)算子使其滿足項目的前后約束，同時對粒子的進(jìn)化速度進(jìn)行必要的修復(fù)。

5）計算粒子適應(yīng)度

6）判斷粒子歷史最優(yōu)位置

根據(jù)粒子適應(yīng)度計算結(jié)果，對比該粒子歷史最優(yōu)位置，若適應(yīng)度更大則取新的適應(yīng)度作為該粒子的歷史最優(yōu)位置，反之，則保留歷史最優(yōu)位置信息。

7）判斷粒子群最優(yōu)位置

對比每個粒子的歷史最優(yōu)位置，取具有最大的適應(yīng)度的粒子作為種群最優(yōu)粒子，其代表的最優(yōu)位置則是資源受限項目調(diào)度的最短工期。

8）進(jìn)化、更新

9）終止條件設(shè)定

考慮進(jìn)化速度和收斂時間限制，采用近似收斂策略，即設(shè)置一個最大進(jìn)化代數(shù)，使得程序運(yùn)行到最大迭代數(shù)后自動停止，把找到的最優(yōu)解作為滿意解。

4 多種資源受限項目調(diào)度的粒子群算法應(yīng)用

本文應(yīng)用基本粒子群算法求解多種資源受限項目管理優(yōu)化調(diào)度問題,以國際標(biāo)準(zhǔn)問題庫PSPLIB[15]中的問題J301-1.SM為例。

4.1 作業(yè)信息表

表1 J301-1.SM的作業(yè)信息表

4.2 參數(shù)設(shè)置

算法編程環(huán)境為VC++，粒子群算法的參數(shù)設(shè)置為：種群數(shù)目50，最大迭代次數(shù)100，認(rèn)知因子c11.8，社會因子c21.8，最大權(quán)重Wmax1.2，最小權(quán)重Wmin0.8，現(xiàn)有的總資源數(shù)A(12)、B(13)、C(4)、D( 12)。

4.3 程序運(yùn)行結(jié)果

圖1 多資源受限最優(yōu)解

圖2 多資源受限粒子迭代過程

表2 粒子群求解的項目調(diào)度方案

5 結(jié)論

由以上程序程序運(yùn)行結(jié)果分析可得：

在滿足資源約束的情況下項目最短工期為39天，從圖2可以看出，在60代左右粒子群即達(dá)到最優(yōu)。在最短項目工期下可以對應(yīng)有不同的調(diào)度方案，如表2所示。項目經(jīng)理可以根據(jù)不同的情況自由的選擇方案，從而更加自由，降低成本。

上面的例子證明，資源約束項目調(diào)度問題可以有效的用粒子群算法來解決。本文提出了一種具體的解決方案以確定有效解空間，從而對解空間進(jìn)行優(yōu)化。每次進(jìn)化后修復(fù)策略,通過修復(fù)算子滿足項目的約束以及資源的限制，通過設(shè)計粒子的適應(yīng)度函數(shù)，拋棄進(jìn)化策略的過程中不符合資源約束的解決方案，只跟蹤滿足項目約束以及資源限制的粒子，以確定最短的工期項目的調(diào)度方案。粒子更新策略可以避免粒子群優(yōu)化算法進(jìn)入局部最優(yōu)解，并能找到滿足項目需求的調(diào)度方案。

［1］De Reyck,B.,Herroelen,W.The multi-mode resource-constrained project scheduling problem with generalized precedence relations[J].European Journal of Operational Research,1999,119(2)：538-556.

［2］Neumann,K.,Schwindt,C.Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production[J].OR Spectrum,1997,44(4)：365-381.

［3］Chen,Y.L.,Rinks,D.,Tang,K.Critical path in an activity network with time constraints[J].European Journal of Operational Research,1997,100(1)：122-133.

［4］李寧,付國江,庫少平,等.粒子群算法的發(fā)展與展望[J].武漢理工大學(xué)學(xué)報：信息與管理工程,2005,27(2)：26-29.

［5］Kennedy J,Eberhart R.Particle Swarm Optimization.Proceedings of IEEE International Conference on Neural Networks[Z].Piscataway：IEEE Service Center, 1995,1942-1948.

［6］Shi Y,Eberhart R C.A modified particle swarm optimizer.Proceedings of IEEE International Conference on Evolutionary Computation[Z].Anchorage,1988：69-73.

［7］Van den Bergh F.An analysis of particle swarm optimizer.Proceedings of the 1988 conference of Evolutionary computation[Z].Piscataway：IEEE Press,1998：67-73.

［8］Mendes R,Kennedy J.The full informed particle swarm：Simpler,maybe better[J].IEEE Transaction on Evolutionary Computation,2004,8(3)：204-210.

［9］AngelineP J.Usingselection toimprove particle swarm optimization.Proceeding of the 1999 Congress on Evolutionary Computation[Z].Piscataway：IEEE Press,1999：84-89.

［10］Higashi N,Iba H.Particle swarm optimization with Gaussian mutation.Proceedings of the 2003 Congress on Evolutionary Computation[Z].Piscataay：IEEE Press,2003：72-79.

［11］Baskar S,Suganthan P N.Anovel concurrent particle swarm optimization.Proceedings of the 2004 Congress on Evolutionary Computation[Z].Piscataay：IEEE Press,2003：792-796.

［12］Al-Kazemi B.Multi-phase particle swarm optimization.Computer Engineering in the Graduate School[J].Syracuse University,2002.

［13］壽涌毅.資源受限多項目調(diào)度的模型與方法[M].杭州：浙江大學(xué)出版社, 2010.9：8-22.

［14］紀(jì)震,廖惠連,吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社,2009：17-19.

［15］KOLISCH R.SPRECHER A.PSPLIB：a project scheduling problemlibrary OR software ORSEP operations research software exchange program [J].European Journal of Operational Research,1997,96(1)：205-216.

郭琦（1988.05—），男，山東乳山人，碩士研究生，上海理工大學(xué)管理學(xué)院，研究方向為設(shè)備管理學(xué).。

曹明明］