基于活動延期風險加權(quán)時差的資源受限項目調(diào)度魯棒性度量

何立華，孔云霄

(中國石油大學(華東)經(jīng)濟管理學院，山東青島266580)

摘要：在項目調(diào)度魯棒性研究中，當活動出現(xiàn)延期風險時，由于各活動性質(zhì)不同，其延期風險權(quán)重也不同，權(quán)重越大的活動越有可能影響項目的完工時間。針對資源受限項目調(diào)度問題，提出一個基于活動延期風險加權(quán)時差的魯棒性度量新指標。在出現(xiàn)不確定因素干擾時，該指標不僅考慮了活動延期風險權(quán)重的影響，同時為實現(xiàn)時差在多個任務之間的共享，還考慮了緊前任務數(shù)量的影響。建立一個以加權(quán)時差最大化為目標的資源受限項目調(diào)度魯棒優(yōu)化模型，并針對模型特點，設計了基于禁忌搜索的模擬退火算法。最后，通過算例驗證了該度量方式和算法的合理性和有效性，對比分析結(jié)果表明所提出的指標優(yōu)于現(xiàn)有的度量指標，較好地滿足了項目調(diào)度質(zhì)量魯棒性的要求。

關鍵詞：項目調(diào)度；魯棒性；延期風險權(quán)重；時差；模擬退火

收稿日期：2014-04-04

基金項目：中央高校基本科研業(yè)務費專項資金(15CX05007B,15CX04102B,15CX08012A,14CX06037B);國家自然科學基金資助項目(71501188);山東省自然科學基金資助項目(ZR2015GM009)

作者簡介：何立華(1971-)，男，安徽懷寧人，博士，副教授，研究方向：管理科學理論與應用、工程項目管理；孔云霄(1989-)，女，山東濟寧人，碩士研究生，研究方向：工程管理與項目管理。

中圖分類號：F224.3;C935 文章標識碼：A

Robustness Measure for the Resource-constrained Project Scheduling

Problem based on Activity Delay Risk Weighted Slack

HE Li-hua, KONG Yun-xiao

(SchoolofEconomicsandManagement,ChinaUniversityofPetroleum(EastChina),Qingdao266580,China)

Abstract:During the research on the robustness of project scheduling, each activity of the project has different weight of delay risk because of its different nature when it appears delay risk. The higher the weight is, the more likely the activity will affect the makespan of the project. In view of the resource-constrained project scheduling problem, a new robustness measure index based on activity delay risk weighted slack is put forward. When uncertain factors appear, this index not only considers influences of the weight of delay risk, but also takes the number of preceding activities into account to realize the share of slack among multiple activities. A robust optimization model for the resource-constrained project scheduling problem aimed at weighted slack maximization is developed. According to the feature of the model, a simulated annealing algorithm based on the tabu search is presented. Finally, the results of the numerical example validate the reasonableness and the effectiveness of the measurement and the algorithm. Also, the superiority of the newly proposed index over the old ones is proven by comparison results and it can meet the demands of quality robustness of the project scheduling better.

Key words:project scheduling; robustness; weight of delay risk; slack; simulated annealing

0引言

伴隨著日益復雜的項目建設環(huán)境，項目在實際運行過程中存在的各種天氣、場地、材料、資源和機械等不確定因素急劇增加，這使得調(diào)度計劃難以按時完成，提高項目調(diào)度的抗干擾能力就成為了項目調(diào)度中的關鍵問題，而魯棒性是衡量項目調(diào)度穩(wěn)定性的重要指標，所以對于資源受限項目調(diào)度問題(resource-constrained project scheduling problem, RCPSP)的魯棒性研究逐漸成為研究的熱點。調(diào)度的魯棒性是指如果一些活動比計劃時間延遲了一些，對于魯棒性的項目調(diào)度，應該能夠抵抗這些由于不可控因素導致的活動時間的小的增加，項目的完成時間具有較好的穩(wěn)定性，并且不必消耗任何成本[1]。

文獻[2～4]認為一個理想的調(diào)度方案應同時具有解的魯棒性和質(zhì)量的魯棒性，質(zhì)量魯棒性(Quality Robustness)是指項目計劃完工時間的穩(wěn)定性；解魯棒性(Solution Robustness)是指活動開始時間的穩(wěn)定性。對于資源約束項目調(diào)度的魯棒性研究，涉及控制理論應用、系統(tǒng)工程思想、運籌學優(yōu)化建模方法及智能優(yōu)化算法，是新興的多學科交叉領域，采用什么樣的度量方式對項目調(diào)度的魯棒性進行度量是其中較為關鍵的核心環(huán)節(jié)[5]。

本文第一部分在描述了項目調(diào)度質(zhì)量魯棒性和解魯棒性的兩種情況之后，通過分析項目計劃過程中具有邏輯關系約束的活動間產(chǎn)生魯棒性調(diào)度的要求，提出以項目活動延期風險權(quán)重大小和前置活動數(shù)量多少作為魯棒性指標來合理分配時差；在第二部分建立了考慮活動延期風險權(quán)重加權(quán)時差的資源受限項目調(diào)度魯棒性優(yōu)化模型；第三部分設計了改進的基于禁忌搜索的模擬退火算法；第四部分是算例對比分析，并在最后提出了該問題的進一步研究方向。

1問題描述

項目調(diào)度的魯棒性有兩種情況：質(zhì)量魯棒性和解魯棒性[1]。至于質(zhì)量魯棒性與解魯棒性的權(quán)衡是根據(jù)項目的性質(zhì)及項目決策者的偏好而定。本文以項目調(diào)度的質(zhì)量魯棒性為研究對象，即使項目活動的實際開始時間比計劃開始時間延遲了些，只要不影響項目的完工時間都認為是魯棒性的調(diào)度。要產(chǎn)生資源受限項目魯棒性的調(diào)度，如何合理的分配時差是核心問題。本文從項目計劃過程中具有邏輯關系約束的活動間產(chǎn)生魯棒性調(diào)度的要求出發(fā)，據(jù)此尋求時差分配的原則。

1.1考慮時序關系約束的時差分配

文獻[8,9]在考慮了項目活動的先后邏輯關系后，提出∑Si*NDSi的魯棒性度量方式，其指標是將時差分配給緊后活動數(shù)量多的項目活動，依據(jù)是緊后活動數(shù)量越多的項目活動受到外界干擾后越可能影響其它的活動，推遲它們的完工時間，從而更有可能影響整個項目的完工日期，所以應使緊后活動數(shù)量多的項目活動得到時差的保障。但是在項目實際執(zhí)行過程中，即使充分保證了緊后活動數(shù)量多的項目活動的穩(wěn)定性，也不能保證其緊后活動不受外界干擾，若將時差都分配給了緊后活動數(shù)量多的項目活動，一旦那些緊后活動受到干擾將必然影響整個項目的工期。反之，若將時差分配給前置活動多的項目活動，即將時差置于各活動之后使時差得到共享，這樣，時差才能流向真正需要的項目活動，保證時差得到充分有效的利用，基于此本文將上述度量方式中的緊后活動數(shù)量(total number of direct successors of activityi,NDSi)改為前置活動數(shù)量(total number of predecessors of activityi,NPi)。

假設某一項目由四個按先后順序進行的活動組成，合同截止工期T=15，資源限量R=5，各活動的工期和資源需求量等參數(shù)如表1所示。如果以∑Si*NDSi為度量目標，則得到的最優(yōu)調(diào)度方案如圖1(a)、(b)、(c)所示。以圖1(a)為例，將時差分配給緊前活動數(shù)量多的項目活動1，這樣一來，在項目實際執(zhí)行過程中，2天的時差只能被活動1所使用，一旦活動1的后置活動2、3、4受到不確定因素的干擾，將直接影響項目的工期，造成項目不能按時完成，也就是說該調(diào)度方案的抗干擾能力差，即魯棒性差。如果以改進的∑Si*NPi為度量目標，則得到的最優(yōu)調(diào)度方案如圖1(d)所示，將時差分配給前置活動數(shù)量多的項目活動4，則在項目實際執(zhí)行過程中，活動4受到干擾可利用此時差，活動1受到干擾同樣可以使用此時差，而且能滿足該項目在截止期限內(nèi)完工，所以此調(diào)度結(jié)果是魯棒性的，同理活動2、3也能利用此時差，也就是說這種調(diào)度方案產(chǎn)生的時差能用于所有的項目活動，使時差在實際執(zhí)行過程中真正流向了需要的活動，在項目活動受到干擾時具有很強的抵抗風險的能力，調(diào)度結(jié)果魯棒性強。因此本文將魯棒性指標改為∑Si*NPi。圖1為不同時差分配下的調(diào)度方案，各調(diào)度方案對比分析結(jié)果如表1所示。

表1　項目一各活動參數(shù)及計算結(jié)果

圖1　項目一不同時差分配下的各調(diào)度方案

1.2考慮延期風險權(quán)重的時差分配

文獻[10]提出了依據(jù)不穩(wěn)定的活動權(quán)重來分配自由時差的思想，其權(quán)重是指活動受干擾影響的成本，其魯棒性指標為∑Wi|E(Si)-Si|，該指標產(chǎn)生的調(diào)度結(jié)果具有解魯棒性。文獻[11]在研究資源約束下的突發(fā)事件應急救援魯棒性調(diào)度優(yōu)化問題時，將魯棒性定義為各活動的時間緩沖與其權(quán)重系數(shù)乘積的總和，即RM=∑λnΔSn。文章指出各救援活動在應急救援過程中所處的位置及面臨的內(nèi)外環(huán)境不同，對于計劃穩(wěn)定性的影響程度也不可能完全相同，為此給每個救援活動定義了一個權(quán)重系數(shù)λn來測度其對于計劃穩(wěn)定性的重要性。

由于項目各活動的性質(zhì)不同，當考慮活動的延期風險時，各活動的延期風險權(quán)重不可能完全相同，延期風險權(quán)重越大的活動越有可能影響項目的完工時間，因此在項目具有時差的情況下，應優(yōu)先將時差分配給延期風險權(quán)重大的活動，這樣就使得最可能影響項目工期的活動有了時差的保證，從而在項目的實際執(zhí)行過程中有效抵抗來自不確定因素的干擾，即項目調(diào)度具有魯棒性。因此在1.1部分提出的指標∑Si*NPi的基礎上，進一步將指標定義為∑Wi*Si*NPi，這里的Wi為各活動的延期風險權(quán)重。

2魯棒性度量方式的模型構(gòu)建

根據(jù)1中問題的描述，假定一個含有N項活動的項目(i∈N,i=1,2,…,N)，活動j為活動i的緊后活動，Ui為活動i的所有緊后活動的集合(j∈Ui)，項目交貨期為T，共需K種可再生資源?；顒觟對第k種資源的需求量為rik，單位時間內(nèi)第k種可再生資源可用量為Rk，各活動的工期和延期風險權(quán)重分別為di和Wi，活動的前置活動數(shù)量記為NPi，設

考慮延期風險權(quán)重加權(quán)時差的資源受限項目調(diào)度魯棒性度量方式模型為：

(1)

(2)

(3)

(4)

xit∈{0,1},?i,t

(5)

其中，式(1)為目標函數(shù)，即以加權(quán)時差最大化為目標；式(2)用以保證各項目活動在計劃工期內(nèi)當且僅當在某一時間完成；式(3)表示項目各活動間的優(yōu)先約束關系；式(4)用以保證每一時刻使用的可更新資源量約束；式(5)表示變量的取值范圍。

3基于禁忌搜索的模擬退火算法設計

資源受限項目調(diào)度問題已被證明為NP-hard問題[12]。模擬退火(Simulated Annealing, SA)算法是一種對NP-hard問題尋優(yōu)求解非常有效的算法[6]。由魯棒串行生成機制[13]產(chǎn)生的初始解和可行解具有較強的隨機性，因此本文采用禁忌搜索算法獲得初始解，這樣在隨后的模擬退火算法最終尋優(yōu)過程中能高效快速地得到最優(yōu)的魯棒性調(diào)度解。

(1)禁忌搜索算法產(chǎn)生魯棒初始調(diào)度

初始化從優(yōu)化結(jié)果O*開始的迭代it及迭代次數(shù)，設置將工期最小為目標所產(chǎn)生的調(diào)度作為初始解，滯空禁忌表，由此生成當前解的領域解，并在領域Ⅰ和Ⅱ內(nèi)根據(jù)自定義值nⅠ和nⅡ進行搜索選出候選解，將滿足活動邏輯關系的解作為當前解，用其對應的對象替換最早進入禁忌表中的對象，更新最優(yōu)解，直至滿足終止準則(工期

禁忌搜索算法步驟如下：

令L*=L,B*=B, O*=O,T=n,it=0, itnoimprove=0

While (工期

for n=1 to nⅠdo：

令O=-999999, it=it+1

for i=2 to n-2, for j=i+1 to n-1 do:

如果滿足活動邏輯關系則交換Li和Lj

if(O>O*and Sn≤δn)or(O=f(B,L)>O′ and it>tabuLi,SLiand it>tabuLj, SLj)

then store i→i′, j→j′, O→O′

如果不滿足活動邏輯關系未交換

if ?i′ and ?j′

then交換Li′和Lj′,tabuLi′,SLi′=tabuLj′,SLj′=it+T

if O′> O*and Sn<δn

then O*=O′ , L*=L, itnoimprove=0

else itnoimprove=itnoimprove+1

for n=1 to nⅡdo：

令O′=-999999, it=it+1, Δbased on itnoimprove

for i=2 to n-1, for b=-Δ to Δ do：

if Bi+ b > 0

then Bi=Bi+b

if(O>O*and Sn≤δn)or(O=f(B,L)>O′and it>tabui,Bi)

then store i→i′, b→b′, O→O′

else

if ?i′ and ?b′

then Bi=Bi+b′, tabui,Bi=it+T

if O′>O* and Sn<δn

then O*=O′, B*=B, itnoimprove=0

else itnoimprove=itnoimprove+1

(2)模擬退火算法尋求最優(yōu)的魯棒性調(diào)度

在算法尋優(yōu)過程中，以魯棒性指標RM最大為目標函數(shù)，從而保證項目魯棒性最大目標的實現(xiàn)，用(1)禁忌搜索產(chǎn)生的優(yōu)解作為當前解S0，并產(chǎn)生領域解Sn，根據(jù)Metropolis準則接受新解，它除了接受優(yōu)化解外，還在一定限度內(nèi)接受惡化解，以保證下一個溫度的搜索不會遺漏較優(yōu)解，但隨著溫度t的減小，就只能接受較少的惡化解，最后在T值趨于零時，就不再接受惡化解了，從而最終得到全局的最優(yōu)解。

模擬退火算法所用到的符號如下：

T0：初始溫度，該溫度應越高越好，以減少接受最差解的可能性

L：馬爾科夫鏈長

S*：最優(yōu)解

RM(S)：魯棒性度量方式評價函數(shù)

P：當領域解不比現(xiàn)行解優(yōu)時接受它的可能性

模擬退火算法步驟如下：

初始化SA的控制參數(shù)(T0，L)

選擇一個初始解，S0

令T=T0,S=S0,S*=S0；計算RM(S0)；

While T>Tmindo:

n=1;

While n

產(chǎn)生S0的領域解Sn;計算Δ=RM(Sn)-RM(S);

if Δ≤0

S=Sn

else

產(chǎn)生一個隨機數(shù)，r∈(0,1);

if(r≤p=e-Δ/T);

S=Sn; n=n+1;

end

end

if RM(S*)≤RM(S)

S*=Sn;

end

end

溫度T衰減；

end

4算例分析

本文引用文獻[10]所采用的算例進行研究。該算例的單代號網(wǎng)絡圖如圖2所示，該項目共有10個活動，活動1和活動10為虛活動，圖中節(jié)點上的數(shù)字分別表示該活動的工期di、資源需求量ri和權(quán)重Wi，資源限量R=8，截止期限T=18。各活動的參數(shù)如表2所示。

圖2　項目二的單代號網(wǎng)絡圖

活動i工期di資源ri權(quán)重Wi權(quán)重歸一化緊后活動數(shù)量NDSi前置活動數(shù)量NPiSi(a)(b)(c)(d)222150.2344100000373100.1563100110434110.1719110000544120.187520012068390.140602320576210.015601010784310.015611011092450.0781023101魯椿性指標∑var(αi)0.2390.0230.0290.163∑Si*NDSi0460∑Wi*Si*NPi1.3120.7490.0161.671

對于該算例，不同優(yōu)化指標得到的不同最優(yōu)調(diào)度方案如圖3 所示。初始調(diào)度方案是以工期最短為目 標函數(shù)所產(chǎn)生的調(diào)度方案，如圖3(a) 所示; 文獻[8，9]中提到的以NDSi 作為度量方式所產(chǎn)生的 調(diào)度方案如圖3(b) 所示，是以指標值最大作為魯棒性最大化的標準; 文獻[13]調(diào)度方案是以所有活動比 值αi 的均方差總和，即ΣVar(αi)作為魯棒性的度量方式，文章指出該指標值越小，表明活動的魯棒性 隨活動工期的分布越合理，如圖3(c) 所示; 本文以作為魯棒性的度量方式產(chǎn)生的調(diào)度方 案如圖3(d) 所示，該魯棒性指標值越大則魯棒性越強。由表2 中數(shù)據(jù)可以看出，在上述不同的度量指標 下所得到的最優(yōu)調(diào)度方案有所不同，采用本文提出的以活動延期風險加權(quán)時差為魯棒性度量指標(= 1．671) 的調(diào)度方案為最優(yōu)調(diào)度方案。

為衡量比較各調(diào)度方案的抗干擾能力，綜合活動延期風險權(quán)重和前置活動數(shù)量兩方面的因素，假設活動4、6、7、9受到不確定因素的干擾，活動工期將會延長，其額外增加的工期分別設為1、1、2、1，其余活動工期不變。受干擾后項目調(diào)度變化情況如圖4所示。由圖4中可以看出，在受到干擾后，各方案的項目工期都有所變化，(a)、(b)、(c)調(diào)度方案工期都增加為19天，超過了項目的截止工期，而本文調(diào)度方案(d)工期為18天，即在截止日期內(nèi)正好完工。從對比分析結(jié)果可以看出，由本文魯棒性指標所產(chǎn)生的調(diào)度方案較其他各優(yōu)化調(diào)度方案具有更高的風險抵抗能力，從而驗證了本文所提魯棒性指標的有效性和優(yōu)越性。

圖4　各調(diào)度方案受干擾后的變化情況

5結(jié)論

針對活動間具有邏輯關系的資源受限項目調(diào)度問題，將時差按前置活動數(shù)量及延期風險權(quán)重來分配，保證了前置活動數(shù)量多、延期風險權(quán)重大的項目活動的魯棒性，這樣有利于抵抗外界干擾因素的影響，使得項目具有很好的質(zhì)量魯棒性。由此提出了基于前置任務數(shù)量和活動延期風險加權(quán)時差的資源受限項目調(diào)度魯棒性指標及相應的優(yōu)化模型，并設計了基于禁忌搜索的模擬退火算法，改進的算法能更有效率地尋得最優(yōu)魯棒調(diào)度解。最后通過算例對比分析各不同魯棒指標的調(diào)度方案，及受干擾后項目的穩(wěn)定性，驗證了該度量方式的有效性與優(yōu)越性，同時也驗證了本文所設計的基于禁忌搜索的模擬退火算法的合理性和有效性。由于本文活動延期風險權(quán)重是直接給定的，而在實際中則需要用一定的科學方法來確定，所以活動延期風險權(quán)重的確定問題將會是另一個有價值的研究方向。

參考文獻：

[1]Al-Fawzan M A, Haouari M. A bi-objective model for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2005, 96(2): 175-187.

[2]Van De Vonder S, Demeulemeester E, Herroelen W, Leus R. The use of buffers in project management: the trade-off between stability and makespan[J]. International Journal of Production Economics, 2005, 97(2): 227-240.

[3]Van De Vonder S, Demeulemeester E, Herroelen W, Leus R. The trade-off between stability and makespan in resource-constrained project scheduling[J]. International Journal of Production Research, 2006, 44(2): 215-236.

[4]Van de Vonder S, Ballestin B, Demeulemeester E, Herroelen W. Heuristic procedures for reactive project scheduling[J]. Computers & Industrial Engineering, 2007, 52(1): 11-28.

[5]王勇勝,梁昌勇.資源約束項目調(diào)度魯棒性研究的現(xiàn)狀與展望[J].中國科技論壇,2009,(8):95-99.

[6]Abbasi B, Shadrokh S, Arkat J. Bi-objective resource-constrained project scheduling with robustness and makespan criteria[J]. Applied Mathematics and Computation, 2006, 180(1): 146-152.

[7]Kobylanski P, Kuchta D. A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2007, 107(2): 496-501.

[8]Chtourou H, Haouarib M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J]. Computers & Industrial Engineering, 2008, 55(1): 183-194.

[9]Khemakhem M A, Chtourou H. Efficient robustness measures for the resource-constrained project scheduling problem[J]. Int. J. Industrial and Systems Engineering, 2013, 14(2): 245-267.

[10]Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules[J]. International Journal of Production Economics, 2008, 111(2): 493-508.

[11]胡信布,何正文,徐渝.基于資源約束的突發(fā)事件應急救援魯棒性調(diào)度優(yōu)化[J].運籌與管理,2013,22(2):72-79.

[12]Blazewicz J, Lenstra J K, Kan A H G R. Scheduling subject to resource constraint: classification and complexity[J]. Discrete Applied Mathematics, 1983(5): 11-24.

[13]龐南生,孟俊姣.多目標資源受限項目魯棒調(diào)度研究[J].運籌與管理,2012,21(3):27-32.