龐南生 白立晨

(華北電力大學經濟與管理學院，北京 102206)

0 引言

項目規(guī)劃階段制定的項目調度計劃是項目的執(zhí)行標準。然而，在項目執(zhí)行過程中往往伴隨著各種不確定性(如客戶提出新的要求、資源供給不足、復雜工藝和不可抗力)，從而導致項目不能按照計劃執(zhí)行。魯棒性項目調度計劃能夠有效考慮項目執(zhí)行過程中的不確定性，在很大程度上提高了項目計劃的穩(wěn)定性。

隨著國內外學者對魯棒性項目調度問題的深入研究，資源流網(wǎng)絡的概念被引入魯棒性項目調度中，認為在結合資源流網(wǎng)絡的情況下制定的魯棒性調度計劃更加合理有效。Artigues等[1]最早提出了資源流網(wǎng)絡的概念，采用拓展并行調度方法生成資源流網(wǎng)絡，但沒有結合計劃的魯棒性。Policella等[2]提出了一個可以從給定的優(yōu)先關系的基準調度中生成資源鏈的調度方法。雖然考慮了計劃的魯棒性，但方法多樣性不足，可能無法選到最優(yōu)方案。Deblaere等[3]提出了MABO (Myopic Activity-Based Optimization)資源流網(wǎng)絡算法，通過選取局部懲罰成本最低的方法產生資源流網(wǎng)絡。此方法在執(zhí)行過程中需要進行大量的仿真，且局部最優(yōu)不一定為全局最優(yōu)，導致生成的資源流網(wǎng)絡方案不夠準確。

針對已有研究的不足，本文提出了一種結合風險傳遞的相關理論，分析對比多條相同工期不同方案的基線計劃，達到選取魯棒性最優(yōu)資源流網(wǎng)絡方案的GRAS(Gert Resource Allocation Scheme)優(yōu)化算法，并通過示例驗證了此方法的有效性。

1 問題描述和提出

1.1 問題描述

假設n個活動組成一個項目網(wǎng)絡，其中開始活動1和結束活動n為虛擬活動，活動1和n的持續(xù)時間為0。項目活動間受制于零延遲的結束-開始的約束關系，活動j(j=1，2，…，n)的持續(xù)時間為dj。每個活動需要一種或多種可更新資源k(k∈K，K={1，2，…，m})，rjK表示活動j對k中資源的需求量，k種資源的總供給量由RK表示，虛擬活動不消耗資源。根據(jù)資源受限項目調度(RCPSP)原理，生成基線調度計劃BS?；€調度計劃確定了活動的開始時間sj(j=0，1，2，…，n)。

圖1a)給出了一個項目網(wǎng)絡示例圖，項目節(jié)點上面左側數(shù)字表示活動的持續(xù)時間，右側數(shù)字表示活動單個可再生資源每個周期的資源需求量。資源類型為每個周期10個資源供給。圖1b)給出了工期最短基線計劃的一種方案。各活動依次開始間為(0，9，0，0，9，17，6，25，15，23，31)。

圖1 項目網(wǎng)絡及調度計劃圖a)項目網(wǎng)絡 b)初始調度計劃

依據(jù)基準計劃，項目執(zhí)行過程中遇到外部干擾很可能出現(xiàn)項目的實際開始時間sj與計劃開始時間sj*不同的情況，而活動的執(zhí)行不能在必要的材料交付到站點之前開始。因此，應該盡可能地制定出穩(wěn)定的計劃，避免活動沖突和資源緊張造成的計劃重排。對于相同的基線計劃，可以產生不同的資源調度方案，每種調度方案對項目魯棒性產生的影響不同。而對于如何選出魯棒性最優(yōu)的調度方案是目前研究的主要方向。

1.2 問題提出

Leus[4](2003)，Leus和Herroelen[5](2004)，Artigues[6](2003)均提出資源在各個活動間的傳遞方式可以由資源流網(wǎng)絡表示的觀點。初始項目網(wǎng)絡由G=(N，A)表示，N為項目活動個數(shù)，A是活動間原始約束關系。如果活動i和活動j之間有約束關系以外的資源流動，則用資源弧AR表示活動i和活動j的資源流動。假設對于每個類型的資源k，虛擬活動中所有資源流出的總和等于所有資源流入虛擬結束活動的總和，等于總可用資源Rk。公式表示如下

(1)

此外，一個可行的資源流網(wǎng)絡必須滿足中間節(jié)點的流量守恒約束。對于每個資源類型k和對于每個非虛擬活動i≠0，i≠n，該活動的總資源流入必須等于該活動的資源總流出，等于該活動的資源需求rik。公式表示如下

(2)

依據(jù)給出的基線計劃生成資源流網(wǎng)絡，達到基線計劃穩(wěn)定性最大化的目的，可以表示為

(3)

E(sj-sj*)表示活動j實際開始時間與計劃開始時間差的期望值，ωj表示活動j的權重。公式(3)表示通過計算項目活動實際開始時間與計劃開始時間偏差的期望值與相應活動的權重乘積的和的最小值判斷項目計劃的穩(wěn)定性。

2 GRAS優(yōu)化算法

以往的資源分配方法均是針對同一條工期最短的基線計劃，產生多種可行的資源分配方案。但是，同一項目工期最短的基線計劃可能不止一條，這就導致在進行資源方案的選擇時，可能選擇的方案并不是最優(yōu)資源分配方案。本文根據(jù)資源受限項目調度原理(RCPSP)，應用隨機調度算法選取多條最短工期不同方案的基線計劃，應用風險傳遞理論原理，依據(jù)各個活動的風險值進行資源分配，并通過對比各方案的懲罰成本選取最優(yōu)的資源分配方案。

2.1 算法原理

項目中各個活動不是單獨存在的，各活動之間是相互影響的，項目網(wǎng)絡圖就是項目間活動關系的一種直接體現(xiàn)。項目執(zhí)行過程中的各種不確定因素即風險不僅影響當前活動，還通過項目間的約束關系影響后續(xù)活動的執(zhí)行，這種項目活動間風險的傳遞為風險傳遞理論[7]。本文在進行資源分配時考慮了項目間的風險傳遞現(xiàn)象，應用圖解評審技術(GERT)計算出各活動的風險值作為資源分配的主要參考指標。項目資源分配時，在有多個活動可為后項活動提供資源時，優(yōu)先選擇風險值小的活動進行資源分配。考慮到項目活動的風險值越大，說明活動不能按計劃完成的可能性越大，對后項活動的按時開工的影響越大，為了保證資源分配后項目調度計劃的穩(wěn)定性最優(yōu)，在進行資源分配時，優(yōu)先由風險值低的活動分配資源。

2.2 關鍵衡量指標

根據(jù)圖解評審技術(GERT)和風險傳遞理論[7]，定義項目工期t為連續(xù)型隨機變量，且隨機變量t服從正態(tài)分布T～(μ，σ2)。對任意實數(shù)s，連續(xù)型隨機變量時間t的矩母函數(shù)為mt(s)，且

(4)

項目活動i和j間的實現(xiàn)概率為ptij=1，活動i和j間的風險傳遞系數(shù)ωtij(s)等于活動間矩母函數(shù)mtij(s)與活動間實現(xiàn)概率ptij之積，且項目調度中均為肯定型輸出節(jié)點，則其實現(xiàn)概率ptij=1。則

ωtij(s)=mtij(s)×ptij

(5)

在項目網(wǎng)絡中，當計算出每一條枝線工序間的傳遞系數(shù)ωtij(s)后，再根據(jù)流線圖計算原理和網(wǎng)絡的基本結構，應用梅森(Mason，S.J.)公式，求解隨機網(wǎng)絡。即將隨機網(wǎng)絡簡化為流線圖，運用流線圖原理進行求解。

梅森公式如下

(6)

式中，Tij為節(jié)點i和j間的等效傳遞系數(shù)；Pk為節(jié)點i到節(jié)點j的第k條線路值，其值等于線路上枝線傳遞系數(shù)的乘積；Δ為流線圖中反映回路組成的特征值，Δ=1-∑(奇階回路值)+∑(偶階回路值)；Δk為流線圖中與第k條線路不接觸的剩余回路的特征值；m為節(jié)點i到節(jié)點j間的線路數(shù)。

項目網(wǎng)絡圖主要由串聯(lián)和并聯(lián)兩種結構類型組成，運用信號流圖原理，從一個節(jié)點到另一個節(jié)點的總傳遞系數(shù)ωij(s)計算公式如下：

(1)串聯(lián)型。從節(jié)點i到節(jié)點j間的結構為串聯(lián)結構，則節(jié)點i到節(jié)點j間的傳遞系數(shù)為

ωiz(s)=ωij(s)×ωjk(s)×…×ωkz(s)

(7)

(2)并聯(lián)型。從節(jié)點i到節(jié)點j間的枝線有n條，n條路為并聯(lián)結構，則節(jié)點i到節(jié)點j間的傳遞系數(shù)為

(8)

根據(jù)網(wǎng)絡結構類型，先求解隨機網(wǎng)絡系統(tǒng)的傳遞系數(shù)WE(s)=PE×ME(s)。根據(jù)矩母函數(shù)的特征，當s=0時，PE=WE(0)，可求出系統(tǒng)兩節(jié)點間的實現(xiàn)概率PE。再根據(jù)公式WE(s)=PE×ME(s)求出矩母函數(shù)ME(s)，從而計算出系統(tǒng)兩節(jié)點間工期實現(xiàn)的風險度λ，計算公式如下

(9)

(10)

(11)

圖1a)給出了一個項目事例，以活動7為例。工期t服從正態(tài)分布T～(μ，σ2)，μ值為各活動工期，為方便計算設σ2=2。根據(jù)公式(4)計算矩母函數(shù)mt(s)，則活動1～3的矩母函數(shù)為mt13(s)=e5s+s2，活動1～4的矩母函數(shù)為mt14(s)=e6s+s2，活動3～7的矩母函數(shù)為mt37(s)=e3s+s2，活動4～7的矩母函數(shù)為mt47(s)=e3s+s2。由于各活動間的實現(xiàn)概率為1，根據(jù)公式(5)，則活動1～3的傳遞系數(shù)ωt13(s)=e5s+s2，活動1～4的傳遞系數(shù)為ωt14(s)=e6s+s2，活動3～7的傳遞系數(shù)為ωt37(s)=e3s+s2，活動4～7的傳遞系數(shù)為ωt47(s)=e3s+s2。

根據(jù)圖1a)可以得出活動1～7有兩條可行路徑，分別為路徑1-3-7和路徑1-4-7。因項目網(wǎng)絡中不存在回路，故活動1～7的傳遞系數(shù)為兩條路徑傳遞系數(shù)之和。根據(jù)公式(6)～公式(8)，路徑1-3-7的傳遞系數(shù)為ωt137(s)=e5s+s2×e3s+s2=e8s+2s2，路徑1-4-7的傳遞系數(shù)為ωt147(s)=e6s+s2×e3s+s2=e9s+2s2，則活動1～7的傳遞系數(shù)為W17=e8s+2s2+e9s+2s2。

2.3 具體步驟

2.3.1 初始工作

①通過串行隨機調度方法，選出工期最短的所有調度計劃，建立初始調度計劃集合{Sn(n=1，2，…，n)}，并將初始調度計劃按照開始時間sj排序，若開始時間sj相等，則按序號升序排列。

②根據(jù)項目網(wǎng)絡圖，計算出各個工作工期的風險度λ。

2.3.2 具體步驟

步驟1：選取一條初始調度計劃S1，根據(jù)計劃開始時間，將開始時間相同的計劃分為一組。依次按照開始時間進行資源分配。在完成一次項目資源分配后，調換同一開始時間活動的順序，再次進行資源分配。

步驟2：判斷活動j的緊前活動是否滿足j的資源需求量，若活動j的緊前活動滿足活動j的資源需求，且緊前活動不唯一時，選取風險度低的活動優(yōu)先分配資源，若風險度相同，則選取資源量大的活動優(yōu)先分配資源，若資源量相同，則按照活動序號依次分配資源。若不滿足，則由活動j前已完成的非緊前活動提供剩余資源。

步驟3：對比活動j前可分配資源的非緊前活動的風險度λ，選取風險度低的活動優(yōu)先分配資源，若不能滿足活動j的資源需求，則選風險度次之的活動繼續(xù)分配資源。若風險度相同，則選取資源量大的活動優(yōu)先分配資源，若資源量相同，則按照活動序號依次分配資源。

步驟4：完成一次資源分配后，計算額外增加資源弧數(shù)量，并計算資源分配計劃的乘法成本(SC)。

步驟5：選出初始調度計劃BS1中額外資源弧數(shù)量最少的資源分配計劃，若額外資源弧數(shù)量相同，則選取懲罰成本最低的資源分配計劃。

步驟6：選取初始調度計劃BS2，重復步驟1-5，直到所有初始調度計劃BSn(n=1，2，…，n)均選出最優(yōu)資源調度計劃。

步驟7：對比各初始調度計劃的資源分配方案，選取額外增加資源弧數(shù)量最少的資源分配計劃，若額外增加資源弧數(shù)量相同，則對比懲罰成本，選取乘法成本最低的方案為最終資源分配方案。

2.4 算例結果

根據(jù)圖1a)所給出的項目調度算例，應用本文提出的GRSA資源流分配方法，通過MATLAB軟件編程計算，得到資源分配方案，生成的資源流網(wǎng)絡如圖2所示。虛線部分表示額外增加的資源約束，數(shù)字表示各個活動間資源的傳遞數(shù)量。

圖2 資源流網(wǎng)絡圖

3 結語

項目資源約束魯棒性的好壞，直接影響整個項目計劃的魯棒性。本文以風險傳遞理論為基礎，設計了基于多條基線計劃的資源分配方法。在資源分配方法中通過對比附加資源約束的數(shù)量和懲罰成本值的大小，選取魯棒性最優(yōu)的資源分配方案，以達到為最終建立魯班性最優(yōu)項目調度計劃打好基礎的目的。