不確定資源約束下項目魯棒性調度算法

摘 要：在跨企業項目中，由于資源可用時間具有不確定性，從而使得項目計劃具有易變性。針對這一問題，首先采用模糊集對項目的不精確時間參數和資源不確定性進行了表示，并在同時考慮調度的質量魯棒性和解的魯棒性情況下，定義了調度的魯棒性度量，進而開發了遺傳算法來求解不確定資源約束下的項目魯棒性調度問題。最后，給出了應用實例，并通過仿真分析說明算法的有效性。該算法已被應用到跨企業項目管理系統中，獲得了良好的效果。

關鍵詞：不確定資源約束；項目調度；魯棒性；優化算法

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)06-2079-04

doi:10.3969/j.issn.1001-3695.2009.06.023

Uncertain resource-constrained project robust scheduling algorithm

ZHANG Hong-guo， XU Xiao-fei， ZHAN De-chen

(School of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China)

Abstract:In cross-enterprise project， uncertainty available times of resources lead to variability of project schedule. In order to solve the problem，represented the imprecise temporal parameters and the uncertainty of the resources involved in project by fuzzy sets，also defined the robustness measure by consideration of quality robustness and solution robustness. Based on these，developeda genetic algorithm for solving the project robust scheduling problem. Finally，presented an example， and illustrated the validity of the algorithm through simulation analysis. The algorithm has been used in a cross-enterprise project management system and works successfully.

Key words:uncertain resource-constrained; project scheduling; robustness; optimization algorithm

資源約束下的項目調度問題（resource-constrained project scheduling problem，RCPSP）是在滿足項目優先約束關系和資源約束的條件下，安排所有任務的開始時間和結束時間，并使得某一性能指標達到最優。RCPSP被廣泛地應用于建筑工程、航空航天、船舶及電站成套設備、軟件開發等大型單件生產類型的企業中^[1]。

隨著經濟全球化和信息技術的高速發展，為了快速響應市場，降低項目的成本和風險，實現優勢互補，多個企業自愿結成聯盟，共同承擔項目工作，從而形成了跨企業項目管理模式^[2，3]。盟員企業間除了緊密協作之外，還具有高度自治性，都有自己獨立的組織體系和決策機制，以及獨立的運作方式和管理方法，而在每個企業內可能存在多個并行項目，因此給聯盟項目所使用的資源的可用時間帶來不確定性，進而使得跨企業項目計劃具有易變性^[4]。在解決RCPSP時必須考慮資源的不確定性約束，以及在資源可用性發生變化時項目調度的魯棒性。

在調度問題的研究中，Graves^[5]首先引入了調度魯棒性的概念，隨后Daniels等人^[6]研究了加工時間具有不確定性的單機魯棒性調度問題。Wang^[7]把魯棒性引入到項目調度中，以在最壞的情況下由一個調度產生的不確定項目周期大于優選的項目周期的機會為魯棒性度量，開發了模糊魯棒性項目調度遺傳算法。Al-Fawzan等人^[8]在項目周期為精確值情況下把魯棒性定義為各活動的松弛時間之和，并以魯棒性最大和項目周期最短為目標，提出了Tabu搜索項目調度算法。Kobylański等人^[9]提出了項目調度的魯棒性分為兩類：第一類是質量魯棒性（quality robustness），指項目計劃制造期，即整個項目的完成時間的穩定性；第二類是解的魯棒性（solution robustness），指調度的細節，即活動的開始時間的穩定性。通過實例分析指出，文獻[8]中以活動松弛時間之和為魯棒性度量是不合適的，并重新定義了調度的魯棒性可通過所有活動時間松弛時間的最小值來度量，并對文獻[8]中的算法進行了改造。然而目前這些研究都沒有考慮資源可用時間的不確定性。

本文基于模糊集理論建立了不確定資源約束下的項目魯棒性調度模型，在此基礎上開發了項目調度遺傳算法，并通過實例分析來驗證所提出的調度算法的有效性。

1 問題描述

在跨企業項目初始計劃階段，通常需要產生一個基線調度，以指導盟員企業實施項目。由于此時處在高層項目計劃階段，通常只考慮精、大、稀、少的關鍵資源約束，該基線調度可歸結為PSm，1，1|prec|γ調度問題^[10]。其含義是項目具有m類可用資源，每類可用資源具有一個處理單元，項目的每個任務至多需要這些資源的一個處理單元，項目的任務之間具有優先約束關系，可通過有向無環網絡圖S=〈V，A〉來表示。其中：V={i|1，2，…，n}是節點（事件）集合；A={(i， j)|i， j∈V}為有向邊（活動）集合。要求在滿足優先關系約束和資源約束的前提下，確定項目各任務在各類資源上的處理時間安排，使得目標性能指標γ最優。

在項目初始計劃階段很難精確地知道項目活動周期，因此活動周期通常是一個估算的模糊值，而且由于資源隸屬于不同的盟員企業，給資源帶來了不確定性，主要體現在資源的可用時間具有模糊性。正是項目活動周期的不確定性和資源可用時間的不確定性，往往會導致在項目執行階段需要變更計劃，從而帶來附加的成本，甚至造成拖期，給項目的成功實施帶來風險，因此在保證滿足優先關系、資源和交貨期約束的前提下，使得產生的調度具有較大的魯棒性是項目基線調度追求的主要性能指標。

1.1 活動模糊周期表示及其運算

在實際的項目計劃中，一般估算出項目任務周期的最短時間、最可能時間和最長時間，因此可把每個任務周期定義為三角模糊數，采用三元組(d1i，d2i，d3i)來表示。

給定兩個三角模糊數分別為=(a1，a2，a3)，=(b1，b2，b3)，則模糊加法、模糊減法Θ和模糊取最小操作∧可分別定義為

=（a1+b1，a2+b2，a3+b3）(1)

Θ=（a1-b3，a2-b2，a3-b1）(2)

在項目調度過程中，在考慮時間約束時，需要比較模糊數的大小。這里采用模糊均值與伸展的方法^[11]。對于模糊數∈F(R)，S()為的支集，模糊均值定義為

()=∫S()xμ(x)dx/

∫S()μ(x)dx(3)

模糊伸展定義為

δ()=[（∫S()x2μ(x)dx/

∫S()μ(x)dx)()2]1/2(4)

當為三角模糊數(t1，t2，t3)時，式(3)和(4)可轉換為

()=(t1+t2+t3)/3 (5)

δ()=((t1-t2)2+(t1-t3)2+(t2-t3)2)1/2/3(6)

采用下面規則來排定兩個模糊數（1和2）的序：

a)如果(1)>(2)，則1>2。

b)如果(1)=(2)且δ(1)>δ(2)，則1>2。

c)如果(1)=(2)且δ(1)=δ(2)，則1=2。

更進一步，模糊集中的最小和最大元素可定義為

min(1，2，…，n)=k，i≠k，k≤i(7)

max(1，2，…，n)=k，i≠k，k≥i(8)

1.2 項目調度的魯棒性度量

在項目活動周期或關鍵資源可用性發生變化時，為了使項目基線調度具有更大的魯棒性，必須同時考慮項目完成時間的穩定性（質量魯棒性）和各活動開始時間的穩定性（解的魯棒性）。為此本文采用所有活動松弛時間的最小值和活動松弛時間的平均值的加權和作為調度魯棒性度量，即

RM=α mini∈N i+(1-α)/NNi=1i(9)

其中: i為活動i的自由松弛時間， i=minj∈succ(i)j-i，i為活動i的計劃完成時間，j為活動j的開始時間，succ(i)為活動i的緊后活動集合；通常α取0.5。

在交貨期約束下，當最大化RM時，則所有活動的松弛時間都將被最大化，因此所有活動的開始時間越穩定，調度解的魯棒性越大，同時項目的質量魯棒性也越大。

1.3 資源不確定性描述及可用性判定

考慮到關鍵資源rk在所屬盟員企業中可能被其他項目占用以及進行大修等，其可用時間k的不確定性可描述為一個具有多段梯形隸屬函數μk(t)的模糊數，即k={(a4j-3k，a4j-2k，a4j-1k，a4jk)|j=1，…，mk}。其中：mk為資源rk的可用時間段數，如圖1所示。

在某一時刻=(t1，t2，t3)，活動i需要關鍵資源rk進行加工，其活動周期為i=(d1i，d2i，d3i)，資源rk的第l段可用時間為(a4l-3k，a4l-2k，a4l-1k，a4lk)，如圖2所示。

在圖2中，如果活動i的所有緊前活動都已完成，則可根據式(9)判斷活動i在資源rk第l段可用時間內是否可調度：

Mik=1 ≥(a4l-3k，a4l-2k，a4l-2k)(+i)≤(a4l-1k，a4l-1k，a4lk)

0otherwise (10)

如果Mik=1，則活動i可以在資源rk上加工處理；否則不能。當活動i被安排在rk上時，活動i的開始和完成時間可按下式計算：

i=(11)

i=i(12)

同時，資源rk的第l段可用時間為

lk=(C2i，C3i，a4l-1k，a4lk)

i＜(a4l-1k，a4l-1k，a4lk)

(0，0，0，0)otherwise (13)

1.4 項目模糊交貨期約束

在最大化項目調度魯棒性的同時，除了要滿足活動優先關系約束和不確定資源約束外，還要滿足項目的交貨期。

項目模糊交貨期的隸屬函數為μ(x)，項目的計劃完成時間為=maxi∈N i，則項目完成時間在交貨期內的可能性度量為=supx min{μ(x)，μ(x)}，如圖3所示。

項目模糊交貨期約束可表現為項目完成時間在交貨期內的可能度()≥λ。其中λ∈[0，1]為可能度的閾值，其取值越大，項目模糊交貨期約束越強。令=(C1，C2，C3)，則()由式(14)確定：

()=1C2≤D1

(D2-C1)/(C2+D2-C1-D1)(C2＞D1)(C1＜D2)

0C1≥D2(14)

2 調度遺傳算法設計

2.1 染色體編碼

由于本文所闡述的調度問題具有復雜的約束，采用基于優先權染色體編碼方法^[12]，即基因的位置表示活動編號，基因值表示優先級。染色體通過解碼來產生一個調度解，在解碼過程中要考慮調度的約束條件，以保證解的合法性。

2.2 解碼算法

根據染色體的優先級表示序列，采用模糊并行調度過程來產生一個調度，該過程描述如下。

符號表示：為當前時間；CS為已被調度并已完成的活動集合；AS為緊前活動已經被調度并已完成的活動集合；DS為在考慮資源約束下可調度的活動集合；PS為正在進行中的活動集合；TS為活動的臨時集合；ri為活動i需要的資源；k為資源k的模糊可用時間；succ(i)為活動i的緊后活動集合；pred(i)為活動i的緊前活動集合。

輸入：p，一個優先級序列（染色體）。

輸出：i，i（i=1，…，n）；魯棒性度量RM；項目完工時間在交貨期內的可能性度量()。

a)初始化，AS←{1}，←(0，0，0)， CS←， DS←，PS←，k=1，…，m，ptrk=1。

b)當CS中活動數小于n時，轉步驟c)；否則，轉步驟m)。

c)對于AS中不占用關鍵資源的活動進行調度，即對于j∈AS且rj=0，令j=，j=j。PS=PS∪{j|j∈AS且rj=0}，AS=AS-{j|j∈AS且rj=0}。

d)資源索引k=1。

e)如果資源索引k≤m，則轉步驟f)；否則，轉步驟k)。

f)令當前資源可用時段索引l=ptrk，DS←。

g)對于j∈AS且rj=k，若≥(a4l-3k，a4l-2k，a4l-2k)(+j)≤(a4l-1k，a4l-1k，a4lk)，則把活動j放入DS中，即DS={j|j∈AS，rj=k，≥(a4l-3k，a4l-2k，a4l-2k)(+j)≤(a4l-1k，a4l-1k，a4lk)}。

h)如果DS≠，則取DS中優先級最高的活動i，即i為滿足p(i)=minj∈DS(p(j))的活動，令i=，i=i，PS= PS∪{i}，AS=AS-{i}，進入步驟i)；否則轉步驟j)。

i)修改當前資源可用時段時間，如果i＜(a4l-1k，a4l-1k，a4lk)，則lk=(C2i，C3i，a4l-1k，a4lk)；否則lk=(0，0，0，0)。

j)k=k+1，轉步驟e)。

k)確定當前時刻，令1=2=3=+∞，取在處理任務中的最小結束時間1=minj∈PSj，取大于當前時刻的最小資源可用時段起時間：2=mink=1，2，…，m{(a4ptrk-3k，a4ptrk-2k，a4ptrk-2k)|

(a4ptrk-3k，a4ptrk-2k，a4ptrk-2k)＞}，取最小下一資源可用時段起時間3=mink=1，2，…，m(a4(ptrk+1)-3k，a4(ptrk+1)-2k，a4(ptrk+1)-2k)，則

=min(1，2，3)。

若(a4(ptri+1)-3i，a4(ptri+1)-2i，a4(ptri+1)-2i)=，則ptri=ptri+1；若j∈PS且j=，則PS=PS-{j}，CS=CS∪{j}，AS=AS∪{i|succ(j)且pred(i)CS}。

l)轉步驟b)。

m)=maxi∈N{i}。

n)j=n。

o)如果j≥1則轉步驟p)；否則轉步驟t)。

p)如果rj=0則轉q)，均衡不占用關鍵資源活動的自由時間；否則轉步驟s)。

q)如果succ(i)=Φ，則=(-j)；否則

=(mini∈succ(j)i-j)。

r）ff=(f1+f2+f3)/3，=(ff，ff，ff)，j=j+/2，j=j+/2。

s)j=j-1，轉步驟o)。

t)按式(14)計算項目完成時間在交貨期內的可能度()。

u)按式(9)計算調度的魯棒性度量RM。

v)結束。

2.3 初始解的產生

基于優先級編碼隨機產生pop-size個個體，每個個體要求滿足項目完成時間在交貨期內的可能度()≥λ，交貨期閾值λ∈[0，1]。其中()如式(14)所示。

2.4 適應值函數

以魯棒性RM(pi)為調度目標，并采用重心法對RM(pi)去模糊化得到第i個個體的適應值：

f(i)=[RM1(pi)+2RM2(pi)+RM3(pi)]/4(15)

2.5 適應值函數

1)選擇策略 采用期望值模型進行個體的選擇。

2)交叉操作 采用期望值模型進行個體選擇后，以交叉率pc進行染色體交叉操作。交叉操作采用兩點交叉方法：從新的種群中隨機選出兩個染色體，在染色體上隨機選擇兩個交叉點，其中一個染色體交叉區間之外與令一染色體交叉區間的值相同的位置用本染色體交叉區間各位置的值順序代替，并交換兩個染色體的交叉區間。例如，給定兩個父染色體p1和p2，用“|”來標定交叉點，令p1=(254|736|81)，p2=(723|541|38)，則交叉操作后，p′1=(273|541|86)，p′2=(524|736|18)。

3)變異操作 以交叉率pc進行染色體交叉操作后，以變異率pm進行染色體變異操作。變異操作采用交換變異方法：在染色體上隨機選擇兩點進行互換。例如，對于染色體p1，選擇位置2和6進行互換，則變異后產生的染色體為p″1=(284|736|51)。

2.6 算法終止條件

要求連續N代適應值無改進即終止算法，本算法N值取60。

3 調度遺傳算法設計

3.1 應用實例

用一個實際的大型水輪發電機制造項目來測試所提出的算法。在該項目的早期計劃階段，只考慮關鍵資源約束、項目各活動之間的約束關系、活動周期以及關鍵資源占用，如圖4所示。其中：R1為6.3 m立車床；R2為9 m立車床；R3為20 m臥車床；R4為250鏜銑床；R5為110數控鏜床。

各資源的模糊可用時間為1={(30 35 110 130)，(160 170 204 209)，(218 225 287 292)，(300 304 345 349)，(356 361 430 460)，(470，477，590，600)};2={(0 0 20 25)，(164 171 200 220)，(226 230 290 310)，(330 345 420 432)};3={(55 58 72 77)，(128 131 142 147)，(200 207 275 279)，(290 297 340 348)，(359 366 395 400)，(410 416 460 465)};4={(85 90 120 126)，(198 204 215 219)，(229 235 273 278)，(290 295 360 366)，(377 384 466 490)};5={(20 23 47 50)，(65 70 88 92)，(120 126 266 273)，(280 285 350 356)，(373 376 470 477)}。交貨期=(500，520)。

利用本文提出的算法進行調度，在交叉率為0.8，變異率為0.2，項目完成時間在交貨期內的可能性要求大于0.8的情況下，其產生的調度結果如表1所示，該去模糊化后的調度魯棒性度量為20.692 3。從結果可以看出，所獲得的調度滿足時間和資源的約束。

3.2 算法分析

對于給定的優先級編碼染色體，其解碼算法即是對項目n個活動在m個關鍵資源上進行調度，當資源發生沖突時，選擇活動所處染色體位置的優先編碼小者優先安排，因此其復雜度為O(n×m)。

為了提高遺傳算法的效率和全局較優性，需選擇適當的交叉率和變異率。在種群規模為50、交貨期閾值為0的情況下，對僅有交叉和僅有變異情況下遺傳算法的收斂值進行了實驗，結果如圖5所示。

由圖5可以看出，只有交叉算子時獲得的解優于只有變異算子時獲得的解，因此在該算法中，交叉算子起決定作用，應選用較大的交叉率和較小的變異率。通過大量的實驗表明，交叉率取0.8、變異率取0.2時，算法的效率和獲得的解較優。在交貨期閾值為0的情況下，其進化過程如圖6所示。在不同交貨期閾值的限制下，獲得的收斂值如表2所示。

本文提出的算法與目前主要項目魯棒性調度算法在約束條件和目標函數的考慮上有所不同，因此進行了定性比較，如表3所示。由表3可以看出，本文提出的算法綜合考慮了項目調度的質量魯棒性和解的魯棒性，并考慮到影響項目調度魯棒性的重要因素——資源的不確定性，因此優于其他算法。

文獻[8]算法解的魯棒性確定資源、活動優先關系確定魯棒性最大

交貨期最短4 結束語

本文針對在跨企業項目中，由于資源的不確定性而導致項目計劃具有易變性的問題，采用模糊集理論對項目的活動時間不確定性和資源不確定性進行了建模，進而以調度的質量魯棒性和解的魯棒性最大為目標函數，并考慮交貨期的約束，開發了不確定資源約束下的項目魯棒性調度遺傳算法。通過大量的實驗表明該算法是有效的，并具有較低的時間復雜度和較好的收斂性，具有一定的理論意義。同時該算法已被應用到實際的跨企業項目計劃系統中，因此具有較大的應用價值。

參考文獻：

［1］TERENCE J，ANDREW A.The maturity of project management in different industries:an investigation into variations between project ma-nagement models［J］.International Journal of Project Management，2003，21(6):471-478.

［2］李巍，尹朝萬，王成恩.分布式網絡化制造中的e-項目管理［J］. 小型微型計算機系統，2003，24(9):1626-1628.

［3］LEE Y H， KUMARA S.Advances in e-manufacturing:foundations of market-based collaborative planning and control of distributed multiple product development projects［J］.Journal of Materials Processing Technology，2003，139(1-3): 178-186.

［4］張宏國，徐曉飛，戰德臣.基于工作分解結構的跨企業項目多級網絡計劃［J］. 計算機集成制造系統，2007，13(3):513-519.

［5］GRAVES S C. A review of production scheduling［J］.Operations Research，1981，29(4):646-675.

［6］DANIELS R L，KOUVELIS P. Robust scheduling to hedge against processing time uncertainty in single-stage production［J］.Management Science，1995，41(2): 363-376.

［7］WANG J. A fuzzy robust scheduling approach for product development projects［J］.European Journal of Operational Research，2004，152(1): 180-194.

［8］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.

［9］KOBYLAN＇SKI 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.

［10］BRUCKER P， DREXL A，ROLF M.Resource-constrained project scheduling:notation， classification， models， and methods［J］.European Journal of Operational Research，1999，112(1):3-41.

［11］LEE E S，LI R L.Comparison of fuzzy numbers based on the probabi-lity measure of fuzzy events［J］.Computers and Mathematics Application，1988，15(10): 887-896.

［12］CHEN Run-wei，GEN M. An evolution programme for the resource-constrained project scheduling problem［J］.International Journal of Computer Integrated Manufacturing，1998， 11(3): 274-287.