魯棒性項(xiàng)目調(diào)度中資源流網(wǎng)絡(luò)優(yōu)化算法研究

龐南生 白立晨

(華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院，北京 102206)

0 引言

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

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

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

1 問(wèn)題描述和提出

1.1 問(wèn)題描述

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

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

圖1 項(xiàng)目網(wǎng)絡(luò)及調(diào)度計(jì)劃圖a)項(xiàng)目網(wǎng)絡(luò) b)初始調(diào)度計(jì)劃

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

1.2 問(wèn)題提出

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

(1)

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

(2)

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

(3)

E(sj-sj*)表示活動(dòng)j實(shí)際開(kāi)始時(shí)間與計(jì)劃開(kāi)始時(shí)間差的期望值，ωj表示活動(dòng)j的權(quán)重。公式(3)表示通過(guò)計(jì)算項(xiàng)目活動(dòng)實(shí)際開(kāi)始時(shí)間與計(jì)劃開(kāi)始時(shí)間偏差的期望值與相應(yīng)活動(dòng)的權(quán)重乘積的和的最小值判斷項(xiàng)目計(jì)劃的穩(wěn)定性。

2 GRAS優(yōu)化算法

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

2.1 算法原理

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

2.2 關(guān)鍵衡量指標(biāo)

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

(4)

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

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

(5)

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

梅森公式如下

(6)

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

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

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

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

(7)

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

(8)

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

(9)

(10)

(11)

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

根據(jù)圖1a)可以得出活動(dòng)1～7有兩條可行路徑，分別為路徑1-3-7和路徑1-4-7。因項(xiàng)目網(wǎng)絡(luò)中不存在回路，故活動(dò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，則活動(dòng)1～7的傳遞系數(shù)為W17=e8s+2s2+e9s+2s2。

2.3 具體步驟

2.3.1 初始工作

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

②根據(jù)項(xiàng)目網(wǎng)絡(luò)圖，計(jì)算出各個(gè)工作工期的風(fēng)險(xiǎn)度λ。

2.3.2 具體步驟

步驟1：選取一條初始調(diào)度計(jì)劃S1，根據(jù)計(jì)劃開(kāi)始時(shí)間，將開(kāi)始時(shí)間相同的計(jì)劃分為一組。依次按照開(kāi)始時(shí)間進(jìn)行資源分配。在完成一次項(xiàng)目資源分配后，調(diào)換同一開(kāi)始時(shí)間活動(dòng)的順序，再次進(jìn)行資源分配。

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

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

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

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

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

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

2.4 算例結(jié)果

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

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

3 結(jié)語(yǔ)

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