基于蟻群算法的資源受限多項目調度問題研究

高 金 郭順生 杜百崗 李西興

（武漢理工大學信息工程學院1） 機電學院2） 武漢 430070）

目前對資源受限的項目調度問題（resourceconstrained project scheduling problem，RCPSP）的研究主要集中于單項目的研究上，對于資源受限 的 多 項 目 調 度 問 題 （resource－constrained multi－project scheduling problem，RCMPSP）通常的處理方式有單項目方式和多項目方式2種［1］.前者是通過人為加入“開始”和“結束”的虛擬活動將多個項目綜合轉變為單個項目求解，而后者則把項目看成獨立的.由于單項目方式忽略了資源在多個項目間的分配與在單個項目內部各活動間的分配的區別，因此存在理論缺陷［2］.

對于多項目方式的研究，研究者從不同的角度，應用不同的技術對該問題進行研究.文獻［3－6］運用遺傳算法進行網絡資源調度，能有效的改進項目調度方案，但是其搜索效率具有一定的隨機性，且在作業數量較大時，會使算法的搜索空間急劇擴大，造成遺傳算法的性能下降［7］.文獻［8］提出一種排序方案，但是該研究沒有提及如何處理作業之間的時序邏輯關系.文獻［9］提出運用粒子群算法的方案，但是當項目任務多時，該算法對于離散的優化可能導致較大的誤差，容易陷入局部最優.文獻［10］提出針對RCMPSP的最大－最小蟻群優化算法，并結合禁忌表能夠很好的防止蟻群算法的停滯現象.

本文基于實際工作背景，分析RCMPSP的特點，結合文獻［11］的案例建立以各項目完成時間最短為目標的數學模型.由于文獻［11］用到的是遺傳算法的思想，因此存在遺傳算法的各種弊端.因此本文根據資源上作業間的時序關系和項目內部任務的緊前關系組成的項目網絡圖，提出運用蟻群算法和串行調度生產機制［12］相結合的方法對該問題求解，并運用禁忌搜索來提高算法的局部搜索能力.為使算法具有實用性，給出算法的基本步驟.結合實例對算法進行測試，通過實例表明，算法能有效的解決資源約束下的多項目調度問題.

1 問題描述

據典型的RCMPSP的描述，本文研究的RCMPSP共包含N個獨立的子項目.各子項目之間沒有必然的聯系，但可能需要占用同一種資源.

每個子項目包含J個任務；其任務按照1到J進行編碼，其中第1和第J個任務為子項目的虛擬起始任務和最終任務，均不占資源和時間；用Aij表示第i個子項目的第j（j＝1，2，…，J）個任務，其工期為dij，任務的開始時間記為STij，完成時間記為FTij；且所有任務一旦開始就不可中斷.子項目的各任務之間存在緊前關系，即各任務只有在其所有緊前任務都結束之后才能開始；任務Aij的緊前任務集合記為Pij.所有項目共享K種可更新資源，其中第k種資源的供應量為Rk；任務Aij對第k種資源的需求量為rkij.

記時刻t正在進行的所有任務的集合為It.則RCMPSP可以表示為如下數學模型

式中：Fi，J為第i個項目的最終完成時間，由于所有項目均從時間0開始，則 max｛Fi，J｝為整個項目組的總工期.式（1）即為RCMPSP的目標函數，最小的項目工期；式（2）表示項目內部各任務之間的緊前關系；式（3）表示在任意時刻所有當前任務對資源的總需求不得超過該資源的供應量.

2 基于RCMPSP的蟻群算法

2.1 混合蟻群算法的設計

由于無資源約束下每個項目活動都有各自的最早開始時間STij和工期dij，則根據串行調度生成機制，能夠得到個階段，每個階段都有一個可行集DJ，在局部可行集中運用蟻群算法的思想，從而實現對RCMPSP的求解.下面對算法的具體求解過程進行說明.

步驟1初始化數據，包括初始化螞蟻的信息素矩陣、算法的啟發式矩陣.

步驟2迭代開始.

步驟3將一只螞蟻放入虛擬起始點.

步驟4求階段J的可行任務集.

步驟5螞蟻根據轉移規則從可行任務集中選擇下一結點，即任務.將選擇任務加入禁忌表中，并更新可行任務集和資源擁有量Rk.其中轉移規則，采用輪盤賭選擇規則；可行任務集表示在J階段k資源上可行的任務集合，根據項目活動的計劃開始時間和完成時間以及任務Aij占用的資源數決定.

步驟6判斷可行任務集是否為空.若非空，則轉至步驟5；否則執行步驟7.

步驟7更新項目任務的計劃開始時間和完成時間.

步驟8如果螞蟻走完所有項目的所有任務，記錄螞蟻的路徑，執行步驟9；否則返回步驟4.

步驟9如果M只螞蟻都走完所有項目的所有任務，執行步驟10；否則返回到步驟3.

步驟10將M只螞蟻的M條路徑的信息素進行揮發，對這M條路徑中完成時間最短的路徑進行信息素增強.且保證所有的信息素濃度在范圍［τmin，τmax］中.

步驟11判斷迭代是不是滿足終止條件，若滿足，則迭代結束；否則返回至步驟2.

2.2 狀態轉移規則

由算法流程可知螞蟻都從起始點開始直到他們走完所有的節點，即螞蟻走完所有項目的所有任務.由于在某一時間內可能存在多個項目任務同時占用某一資源，但資源不能同時滿足所有項目任務的需求時，如何選擇優先執行是算法的關鍵.由蟻群算法的思想可知螞蟻會根據隨機選擇規則進行選擇.計算公式為

式中：pJA為階段J選擇活動A的概率；ηJA為階段J活動A的啟發信息由式（6）計算；τJA為階段J活動A的信息素濃度，由信息素更新機制得到；DkJ為螞蟻在資源k上階段J的可行集，由串行調度生成機制得到.

式中：stA為活動A的開始時間；DJ為階段J的可行集.

2.3 信息素更新規則

當所有螞蟻都遍歷完所有的項目任務，所有的項目任務的信息素將發生更新.根據實際的螞蟻可知，信息素的更新方式主要包括信息素揮發和信息素加強.首先當螞蟻遍歷所有項目任務時，信息素會按照一定的比例進行信息素揮發，揮發量由下式給出

式中：ρ為揮發強度，0＜ρ＜1.

在迭代中，為了突出螞蟻的最佳路徑在下次迭代中被選擇概率，只對最佳路徑上的信息素濃度進行加強，即最佳的項目調度的信息素得到加強.加強方式如下

式中：ΔτbsJA為迭代中最佳的項目調度增加的信息素.

式中：Q為螞蟻的信息素總量，為一常數；Cbs為最佳路徑的距離，這里表示項目調度中，最短的完成時間.

然而，由于在一次迭代中可能存在所有的螞蟻都選擇同一種調度方案，從而導致這個調度方案的信息素增加太快，以致發生停滯現象，影響最優解的求得.為了避免這種現象的發生，本文采用最大最小蟻群算法，將信息素濃度控制在［τmin，τmax］中.

式中：a為常數.

2.4 可行任務集DJ

由算法流程圖可知，可行任務集DJ是算法的重要參數，它的擴展包含了整個項目調度的所有的解空間，如何求可行任務集DJ是算法的重點.根據Kelley的串行調度生成機制，對于包含N個項目的RCMPSP來說，一共包含個任務，因此對于RCMPSP的串行調度生成機制，需要個階段.在每一階段中，首先要確定可行集DJ，根據一定的優先規則從DJ中選取任務，并在滿足式（2）、（3）的條件下進行調度.通過局部擴展，逐步更新可行集，從而得到整個項目的進度安排.

由于每個項目都有各自的計劃開始時間，于是將各項目任務按計劃開始時間分配到對應資源k上，如圖1所示3個項目活動在資源k上的計劃進度安排.由圖可知項目1和項目2最早開始發生資源沖突，則在此沖突持續時間段內的所有項目任務即為此階段的可行任務集DJ.

圖1 資源沖突

3 實例仿真與分析

實例模型采用文獻［11］的模具生產項目，即3個具有相同結構的并行執行項目，網絡結構見圖2.每個項目有16個任務，一共48個任務，占用9種資源，且每個項目任務只占用一種資源，不同的項目任務的執行時間不同.項目任務在無資源約束下的計劃開始時間、工期和占用資源數量見表1.

圖2 項目網絡圖

表1 項目活動無資源約束下的開始時間和工期及占用資源數量

根據設計的蟻群算法的思想，在迭代次數NC＝100，揮發系數ρ＝0.1，偏重因子α＝0.3，β＝8的設置下可以得到一個可行的調度計劃，見表2.由表2可知，項目組的總的完成時間為61 d，比文獻［11］少1d，說明此算法的設計在資源受限的多項目調度方面存在一定的優勢，能夠提高企業的項目調度效率.

4 結束語

針對資源受限的多項目調度問題的特征，運用串行進度生產機制和蟻群算法的基本思想，設計出一種混合的蟻群算法.為了避免蟻群算法的停滯現象，該算法采用最大最小蟻群算法中對信息素的濃度進行限制的方法，從而有效的提高算法較優解的選取.通過實例的演算與分析發現此算法能夠較好的解決RCMPSP問題.

表2 資源約束下的調度計劃 d

［1］BROWNING T R，YASSINE A A.Resource－constrained multi－project scheduling：priority rule performance revisited［J］.International Journal of Production Economics，2010（2）：212－228.

［2］WILEY V D，DECKRO R F，JACKSON Jr J A.Optimization analysis for design and planning of multiproject programs［J］.European Journal of Operational Research，1998（2）：492－506.

［3］GONCALVES J F，MENDES J J M，RESENDE M G C.A genetic algorithm for the resource constrained multi－project scheduling problem［J］.European Journal of Operational Research，2008（3）：1171－1190.

［4］應 瑛，壽涌毅，李 敏.資源受限多項目調度的混合遺傳算法［J］.浙江大學學報：工學版，2009（1）：23－27.

［5］李 敏.資源約束下多項目調度問題遺傳算法研究［D］.杭州：浙江大學，2008.

［6］VALLS V，BALLESTIN F，QUINTANILLA S.A hybrid genetic algorithm for the resource－constrained project scheduling problem［J］.European Journal of Operational Research，2008（2）：495－508.

［7］林 琳，姚 郁.多資源約束下的多項目作業調度問題研究［J］.哈爾濱工業大學學報，2007（7）：1045－1049.

［8］REMY J.Resource constrained scheduling on multiple machines［J］.Information Processing Letters，2004（91）：177－182.

［9］楊 銘，王 凱，李 原，等.基于改進型粒子群算法的航空多項目調度方法［J］.火力與指揮控制，2010（2）：55－58.

［10］MCRKLC D，MIDDCNDORF M，SCHMCCK H.Ant colony optimization for resource－constrained project scheduling［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：333－318.

［11］廖 仁，陳慶新，毛 寧.模具虛擬企業項目調度遺傳算法研究［J］.計算機集成制造系統，2004（7）：80－84.

［12］KELLEY J E.The critical path method：resources planning and scheduling［J］.New Jersey Industrial Scheduling USA：Prentice Hall，1963（1）：347－365.