基于活動延期風險加權時差的資源受限項目調度魯棒性度量

基于活動延期風險加權時差的資源受限項目調度魯棒性度量

何立華，孔云霄

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

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

關鍵詞：項目調度；魯棒性；延期風險權重；時差；模擬退火

收稿日期：2014-04-04

基金項目：中央高校基本科研業務費專項資金(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引言

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

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

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

1問題描述

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

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

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

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

表1　項目一各活動參數及計算結果

圖1　項目一不同時差分配下的各調度方案

1.2考慮延期風險權重的時差分配

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

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

2魯棒性度量方式的模型構建

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

考慮延期風險權重加權時差的資源受限項目調度魯棒性度量方式模型為：

(1)

(2)

(3)

(4)

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

(5)

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

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

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

(1)禁忌搜索算法產生魯棒初始調度

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

禁忌搜索算法步驟如下：

令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)模擬退火算法尋求最優的魯棒性調度

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

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

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

L：馬爾科夫鏈長

S*：最優解

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

P：當領域解不比現行解優時接受它的可能性

模擬退火算法步驟如下：

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

選擇一個初始解，S0

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

While T>Tmindo:

n=1;

While n

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

if Δ≤0

S=Sn

else

產生一個隨機數，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]所采用的算例進行研究。該算例的單代號網絡圖如圖2所示，該項目共有10個活動，活動1和活動10為虛活動，圖中節點上的數字分別表示該活動的工期di、資源需求量ri和權重Wi，資源限量R=8，截止期限T=18。各活動的參數如表2所示。

圖2　項目二的單代號網絡圖

活動i工期di資源ri權重Wi權重歸一化緊后活動數量NDSi前置活動數量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

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

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

圖4　各調度方案受干擾后的變化情況

5結論

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

參考文獻：

[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]王勇勝,梁昌勇.資源約束項目調度魯棒性研究的現狀與展望[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]胡信布,何正文,徐渝.基于資源約束的突發事件應急救援魯棒性調度優化[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]龐南生,孟俊姣.多目標資源受限項目魯棒調度研究[J].運籌與管理,2012,21(3):27-32.