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

高 金 郭順生 杜百崗 李西興

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

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

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

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

1 問(wèn)題描述

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

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

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

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

2 基于RCMPSP的蟻群算法

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

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

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

步驟2迭代開始.

步驟3將一只螞蟻放入虛擬起始點(diǎn).

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

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

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

步驟7更新項(xiàng)目任務(wù)的計(jì)劃開始時(shí)間和完成時(shí)間.

步驟8如果螞蟻?zhàn)咄晁许?xiàng)目的所有任務(wù)，記錄螞蟻的路徑，執(zhí)行步驟9；否則返回步驟4.

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

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

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

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

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

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

式中：stA為活動(dòng)A的開始時(shí)間；DJ為階段J的可行集.

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

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

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

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

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

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

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

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

2.4 可行任務(wù)集DJ

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

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

圖1 資源沖突

3 實(shí)例仿真與分析

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

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

表1 項(xiàng)目活動(dòng)無(wú)資源約束下的開始時(shí)間和工期及占用資源數(shù)量

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

4 結(jié)束語(yǔ)

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

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

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

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

［9］楊 銘，王 凱，李 原，等.基于改進(jìn)型粒子群算法的航空多項(xiàng)目調(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è)項(xiàng)目調(diào)度遺傳算法研究［J］.計(jì)算機(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.