基于粒子群算法的多類資源受限項目調度

郭琦

（上海理工大學 管理學院，中國 上海200093）

基于粒子群算法的多類資源受限項目調度

郭琦

（上海理工大學 管理學院，中國 上海200093）

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

項目調度；資源受限；粒子群算法

0 引言

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

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

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

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

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

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

1 問題描述

資源受限項目調度問題[13]（resource-constrained project scheduling problem,RCPSP）,或稱資源約束下項目調度問題，即要求在滿足項目內部優先關系和資源約束的前提下，合理安排項目的進度計劃，從而優化項目預期目標。

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

2 粒子群算法

2.1 算法簡介

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

2.2 粒子群優化算法的數學模型

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

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

3 多種資源受限項目調度問題求解

粒子群算法的具體步驟：

1）確定不違反緊前，緊后關系

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

3）粒子群初始化

4）修復

在初始化后或進化后，應檢驗粒子是否滿足項目前后約束和開始時間約束條件，使各活動的實際開始時間滿足網絡計劃的前后約束關系，若不滿足，則采用修復策略，通過修復算子使其滿足項目的前后約束，同時對粒子的進化速度進行必要的修復。

5）計算粒子適應度

6）判斷粒子歷史最優位置

根據粒子適應度計算結果，對比該粒子歷史最優位置，若適應度更大則取新的適應度作為該粒子的歷史最優位置，反之，則保留歷史最優位置信息。

7）判斷粒子群最優位置

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

8）進化、更新

9）終止條件設定

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

4 多種資源受限項目調度的粒子群算法應用

本文應用基本粒子群算法求解多種資源受限項目管理優化調度問題,以國際標準問題庫PSPLIB[15]中的問題J301-1.SM為例。

4.1 作業信息表

表1 J301-1.SM的作業信息表

4.2 參數設置

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

4.3 程序運行結果

圖1 多資源受限最優解

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

表2 粒子群求解的項目調度方案

5 結論

由以上程序程序運行結果分析可得：

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

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

［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］李寧,付國江,庫少平,等.粒子群算法的發展與展望[J].武漢理工大學學報：信息與管理工程,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］壽涌毅.資源受限多項目調度的模型與方法[M].杭州：浙江大學出版社, 2010.9：8-22.

［14］紀震,廖惠連,吳青華.粒子群算法及應用[M].北京：科學出版社,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—），男，山東乳山人，碩士研究生，上海理工大學管理學院，研究方向為設備管理學.。

曹明明］