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

高 金 郭順生 杜百崗 李西興

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

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

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

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

1 問題描述

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

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

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

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

2 基于RCMPSP的蟻群算法

2.1 混合蟻群算法的設(shè)計

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

步驟1初始化數(shù)據(jù)，包括初始化螞蟻的信息素矩陣、算法的啟發(fā)式矩陣.

步驟2迭代開始.

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

步驟4求階段J的可行任務(wù)集.

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

步驟6判斷可行任務(wù)集是否為空.若非空，則轉(zhuǎn)至步驟5；否則執(zhí)行步驟7.

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

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

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

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

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

2.2 狀態(tài)轉(zhuǎn)移規(guī)則

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

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

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

2.3 信息素更新規(guī)則

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

式中：ρ為揮發(fā)強度，0＜ρ＜1.

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

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

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

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

式中：a為常數(shù).

2.4 可行任務(wù)集DJ

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

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

圖1 資源沖突

3 實例仿真與分析

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

圖2 項目網(wǎng)絡(luò)圖

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

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

4 結(jié)束語

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

表2 資源約束下的調(diào)度計劃 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］應(yīng) 瑛，壽涌毅，李 敏.資源受限多項目調(diào)度的混合遺傳算法［J］.浙江大學(xué)學(xué)報：工學(xué)版，2009（1）：23－27.

［5］李 敏.資源約束下多項目調(diào)度問題遺傳算法研究［D］.杭州：浙江大學(xué)，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］林 琳，姚 郁.多資源約束下的多項目作業(yè)調(diào)度問題研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2007（7）：1045－1049.

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

［9］楊 銘，王 凱，李 原，等.基于改進型粒子群算法的航空多項目調(diào)度方法［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］廖 仁，陳慶新，毛 寧.模具虛擬企業(yè)項目調(diào)度遺傳算法研究［J］.計算機集成制造系統(tǒng)，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.