魏亞鋒，張夢茹，蘇志雄

(南昌工程學(xué)院 工商管理學(xué)院，江西 南昌 330099)

資源受限項(xiàng)目調(diào)度問題(RCPSP)作為一類NP-hard問題一直備受項(xiàng)目管理人員和學(xué)者的關(guān)注。RCPSP主要研究在資源以及工期約束的情況下，如何合理地安排各個工序間的優(yōu)先關(guān)系以實(shí)現(xiàn)預(yù)期的目標(biāo)?，F(xiàn)有的關(guān)于RCPSP的研究大多是在確定性環(huán)境下進(jìn)行的[1]，即假設(shè)項(xiàng)目中各工序的工期、所需資源等都是確定的。然而，在實(shí)際執(zhí)行過程中，由于受到各種不確定因素的影響，大多數(shù)的項(xiàng)目在實(shí)施過程中都存在一定程度的不確定性。例如工序工期的延期或中斷、資源可用量的減少或者設(shè)備的維修等，都會干擾項(xiàng)目的正常進(jìn)行，進(jìn)而造成工序間優(yōu)先關(guān)系以及資源流的變化，導(dǎo)致基準(zhǔn)進(jìn)度計劃的推遲或者中斷。因此，應(yīng)考慮不確定因素的資源受限項(xiàng)目調(diào)度問題[2]，即在滿足項(xiàng)目工期和資源約束的前提下，如何合理安排工序間的優(yōu)先關(guān)系。在項(xiàng)目面對干擾時，生成一個具有較高的魯棒性的調(diào)度計劃逐漸成為項(xiàng)目調(diào)度領(lǐng)域研究的熱點(diǎn)。現(xiàn)有的關(guān)于RCPSP的研究大多是基于CPM網(wǎng)絡(luò)計劃，但是在CPM網(wǎng)絡(luò)計劃中，工序間優(yōu)先關(guān)系的表示方式單一，不能很好地描述工序間復(fù)雜的關(guān)系網(wǎng)絡(luò)。廣義優(yōu)先關(guān)系(GPRs)[3]很好的彌補(bǔ)了CPM網(wǎng)絡(luò)的這一不足，因此本文選擇以廣義優(yōu)先關(guān)系作為網(wǎng)絡(luò)計劃的工具，進(jìn)一步擴(kuò)展了工序間優(yōu)先關(guān)系的表示方法。

經(jīng)過多年的發(fā)展，對項(xiàng)目調(diào)度問題的研究已經(jīng)取得了不少研究成果。Herroelen[4]等根據(jù)項(xiàng)目所處的階段，在制定項(xiàng)目計劃時將不確定環(huán)境下項(xiàng)目調(diào)度分為兩種情況，即前攝性項(xiàng)目調(diào)度問題和反應(yīng)性項(xiàng)目調(diào)度問題。根據(jù)對擾動的處理方法的不同，何正文[5]等將現(xiàn)有的研究分為前攝性調(diào)度方法、反應(yīng)性調(diào)度方法以及關(guān)鍵鏈方法等。除了對項(xiàng)目調(diào)度中的問題的研究之外，王凌[6]等根據(jù)不確定資源受限項(xiàng)目調(diào)度中存在的大規(guī)模、強(qiáng)約束、多目標(biāo)和不確定性等諸多復(fù)雜性，導(dǎo)致模型求解困難的問題，對資源受限項(xiàng)目調(diào)度的求解算法進(jìn)行的深入研究，提出了多種求解算法。

前攝性資源受限項(xiàng)目調(diào)度問題是在項(xiàng)目開始之前，在事先考慮各種不確定因素的影響下，在進(jìn)度計劃中加入一定的緩沖，生成一個具有魯棒性的基準(zhǔn)進(jìn)度計劃，使得項(xiàng)目在面臨干擾時具有一定的穩(wěn)定性。針對前攝性項(xiàng)目調(diào)度方法如今已經(jīng)有了廣泛的研究和應(yīng)用，Lambrechts[7]等針對資源可用量問題研究了隨機(jī)資源中斷問題的前攝性和反應(yīng)性調(diào)度策略。李雪[8]等考慮了魯棒成本的多模式雙目標(biāo)問題并設(shè)計了相應(yīng)的前攝性求解模型和算法。馬詠[9]等對具有隨機(jī)活動工期和柔性資源約束的前攝性項(xiàng)目調(diào)度優(yōu)化問題進(jìn)行了研究和求解。蘇志雄[10]等針對在帶有廣義優(yōu)先關(guān)系(簡稱GPRs)的項(xiàng)目中尚缺乏對這兩類時差的分析計算，從多視角研究GPRs下工序共用時差的量化及特性。

在模型求解方面，包含不確定性的RCPSP問題求解主要由精確解算法和啟發(fā)式算法組成?；跀?shù)學(xué)模型求解精確解的算法主要以分支定界算法為主，即將解空間用樹形結(jié)構(gòu)劃分為多個子空間，不斷通過各個子空間的最大或最小值來縮小搜索范圍；由于不確定RCPSP問題的解空間隨著項(xiàng)目中工序數(shù)量的增加呈指數(shù)增長。為了應(yīng)對大規(guī)模問題的求解，除了求解精確解的方法之外采用啟發(fā)式規(guī)則快速獲得問題的解的啟發(fā)式算法在大規(guī)模問題上得到了廣泛的應(yīng)用，其主要包括禁忌搜索算法[11]、蝙蝠算法[12]等，但是啟發(fā)式算法只是得到相對的最優(yōu)解，而不能得到實(shí)際意義上的最優(yōu)解。

當(dāng)前，國內(nèi)外對廣義優(yōu)先關(guān)系(GPRs)條件下網(wǎng)絡(luò)計劃的研究主要集中在項(xiàng)目調(diào)度領(lǐng)域。Neumann[13]等利用分支定界方法對資源受限項(xiàng)目調(diào)度問題進(jìn)行求解。蘇志雄[14]等針對GPRs條件下的時間費(fèi)用權(quán)衡問題，提出了相應(yīng)的求解方法并對廣義優(yōu)先關(guān)系下的隱性時間、隱性時差和偽時差進(jìn)行了研究并給出了參數(shù)值的正確算法。Wei[15]等對廣義優(yōu)先關(guān)系條件下的離散化時間成本權(quán)衡的截止時間問題進(jìn)行了研究并提出了一種求解大規(guī)模復(fù)雜問題的有效算法。

本文基于項(xiàng)目調(diào)度理論，在廣義優(yōu)先關(guān)系條件下，考慮工期和其他因素的不確定性導(dǎo)致項(xiàng)目在執(zhí)行過程中偏離基準(zhǔn)進(jìn)度計劃甚至導(dǎo)致項(xiàng)目中斷的問題。為了使基準(zhǔn)進(jìn)度計劃在滿足項(xiàng)目工期約束的前提下具有較高的抵御不確定性干擾的能力，本文在資源和優(yōu)先關(guān)系的約束下，構(gòu)建了以魯棒性最大化以及項(xiàng)目工期最小化為目標(biāo)的多目標(biāo)前攝性資源受限項(xiàng)目調(diào)度模型。

1 問題描述

由于各種不確定因素的存在，項(xiàng)目在執(zhí)行之前，項(xiàng)目管理人員會在考慮各種干擾的情況下，基于工序工期均值E(di)生成一個基準(zhǔn)進(jìn)度計劃。假設(shè)一個項(xiàng)目中共有n+2個工序，其中工序0和工序n+1為虛工序，即項(xiàng)目的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)。項(xiàng)目實(shí)施總共需要K種可更新資源，其中第k(k=1，2，…，K)種資源的總供應(yīng)量為Rk，其中工序i對第k種資源的需求量為qik。由于在項(xiàng)目實(shí)際執(zhí)行過程中各種不確定干擾的存在，可能會導(dǎo)致項(xiàng)目中工序的工期在一定范圍內(nèi)波動。因此，項(xiàng)目中各工序的工期并不是一個固定值。一般來說，工序i工期用其期望值E(di)來表示，用其標(biāo)準(zhǔn)差δi表示工序i的工期的波動，各工序工期的期望和標(biāo)準(zhǔn)差均是基于該工序的歷史數(shù)據(jù)求得的。其中工序0和工序n+1工期的均值以及標(biāo)準(zhǔn)差均為0。

在GPRs網(wǎng)絡(luò)中，工序間優(yōu)先關(guān)系的表述方式不僅僅局限于“開始—結(jié)束”關(guān)系類型，GPRs網(wǎng)絡(luò)對工序間優(yōu)先關(guān)系的類型進(jìn)行了進(jìn)一步的擴(kuò)展，具體類型如表1所示。

表1 GPRs下工序間優(yōu)先關(guān)系的類型

2 模型構(gòu)建

由于項(xiàng)目中各資源的總的供應(yīng)量為Rk，并且虛工序0和n+1分別為項(xiàng)目的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)，不同于以往文獻(xiàn)中虛工序?qū)τ谫Y源需求為零的假定。為了保證項(xiàng)目在各個時期各種資源流動的總量不高于各資源的總供應(yīng)量，本文假定項(xiàng)目中各資源均從開始節(jié)點(diǎn)流出并最終流入結(jié)束節(jié)點(diǎn)，即虛工序0和n+1對各種可更新資源的需求量為各資源的總供應(yīng)量Rk，即

(1)

現(xiàn)假定一個項(xiàng)目的基準(zhǔn)進(jìn)度計劃為P=(S，D)，其中S=(s0，…，sn+1)和D=(d0，…，dn+1)分別為各工序計劃開始時間si和工期均值E(di)的集合，其中s0=d0=dn+1=0。然而項(xiàng)目在實(shí)際執(zhí)行過程中，項(xiàng)目中各工序工期的實(shí)際值并不一定完全等于期望值。因此，為了使生成的調(diào)度計劃具有一定的穩(wěn)定性，項(xiàng)目管理人員通常會采用加入緩沖的機(jī)制來增加基準(zhǔn)進(jìn)度計劃的穩(wěn)定性。在進(jìn)度計劃中加入的緩沖機(jī)制主要包括資源緩沖[16]和時間緩沖[17]兩種。由于本文主要考慮資源受限情況下，對項(xiàng)目的基準(zhǔn)進(jìn)度計劃的影響，因此本文采用在工序中加入時間緩沖的方法來增加項(xiàng)目基準(zhǔn)進(jìn)度計劃的穩(wěn)定性。

在GPRs網(wǎng)絡(luò)中，項(xiàng)目中各工序的優(yōu)先關(guān)系有多種表示方式，因此，各工序擁有多個時間參數(shù)。在考慮項(xiàng)目總工期最小化的前提下，為了增加基準(zhǔn)進(jìn)度計劃的穩(wěn)定性，本文用工序的計劃最遲開始時間(LSi)減去其計劃開始時間(si)，即在不影響項(xiàng)目預(yù)定的總工期的前提下工序i的開始時間最多能推遲的時間表示工序的時間緩沖Δi，其中

Δi=LSi-si.

(2)

項(xiàng)目在實(shí)際執(zhí)行過程中，由于工期的波動或者其他預(yù)料之外的因素，會造成工序的實(shí)際結(jié)束時間偏離基準(zhǔn)進(jìn)度計劃中的結(jié)束時間，只要其偏離程度不大于時間緩沖，其后續(xù)工序就仍可以按照基準(zhǔn)進(jìn)度計劃正常執(zhí)行。

(3)

在RCPSP的一般模型中，模型的目標(biāo)函數(shù)為最小化項(xiàng)目的總工期。本文在總工期最小化的目標(biāo)的基礎(chǔ)上，增加了魯棒性最大化的目標(biāo)函數(shù)，其中項(xiàng)目中各工序的魯棒性指標(biāo)為robui，用工序的權(quán)重因子與該工序的時間緩沖的大小的乘積來表示，即

robui=ξiΔi，

(4)

進(jìn)而對各個工序的魯棒性的值進(jìn)行求和得到整個項(xiàng)目的總的魯棒性為

(5)

在上述對問題描述的基礎(chǔ)上，針對本文所提問題構(gòu)建如下的前攝性資源受限項(xiàng)目調(diào)度模型：

(6)

Minsn+1，

(7)

s.t.

sn+1≤LSn+1，

(8)

si+di≤sj+B(1-zij)(1-aij)?i，j∈A∪R，

(9)

LSi+di+B(zij-1)(aij-1)≤LSj?i，j∈A∪R，

(10)

rijk≤B(zij+aij)?i，j∈A?k，

(11)

(12)

(13)

di≥0；rijk≥0；

(14)

zij∈{0，1}

(15)

目標(biāo)函數(shù)(6)為基準(zhǔn)進(jìn)度計劃的總工期最小化；目標(biāo)函數(shù)(7)為基準(zhǔn)進(jìn)度計劃的魯棒性指標(biāo)最大化，使基準(zhǔn)進(jìn)度計劃具有較高穩(wěn)定性。約束條件(8)為項(xiàng)目工期的限制，保證基準(zhǔn)進(jìn)度計劃的工期不超過項(xiàng)目的完工期限，其中項(xiàng)目的工期等于虛工序n+1的最遲結(jié)束時間；約束條件(9)為工序間優(yōu)先關(guān)系約束；約束條件(10)為各工序的最遲開始時間約束；約束條件(11)為項(xiàng)目中各工序間優(yōu)先關(guān)系以及資源流之間聯(lián)系的約束，如果工序i和工序j之間有資源流動則zij=1，若zij=0則工序i和工序j之間的不存在資源流動；約束條件(12)為資源總量約束，保證項(xiàng)目的資源流入量等于項(xiàng)目的資源流出量等于各資源的總的可用量；約束條件(13)為資源流約束，保證各工序上各種資源的總流出量等于總流入量；約束條件(14)～(15)為決策變量的定義域，保證各工序的工期、資源流為非負(fù)整數(shù)。

本文所提出的模型可以看作為資源受限項(xiàng)目調(diào)度問題(RCPSP)，由于資源受限項(xiàng)目調(diào)度問題的NP-hard性質(zhì)[18]，因此，本文所提出的模型必然為NP-hard問題。針對NP-hard問題的求解可以選擇采用獲得精確解的算法或者求得近似解的算法。由于模型中的決策變量為整數(shù)和0～1變量，因此本文提出的前攝性資源受限調(diào)度模型為整數(shù)規(guī)劃模型。前攝性調(diào)度模型主要用來生成基準(zhǔn)進(jìn)度計劃，基準(zhǔn)進(jìn)度計劃的優(yōu)劣會對整個項(xiàng)目在實(shí)際執(zhí)行過程中的穩(wěn)定性產(chǎn)生直接影響。因此，在對前攝性資源受限項(xiàng)目調(diào)度模型進(jìn)行求解時，為了得到模型的最優(yōu)解，本文采用線性松弛和分支定界算法，在可接受的求解時間內(nèi)求得基準(zhǔn)進(jìn)度計劃的精確解，然后對其進(jìn)行可行性修正。

3 算例生成及測試

本文采用分支定界算法對所建立的模型進(jìn)行求解，但是相比于啟發(fā)式算法，分支定界等精確算法一般只適用于小規(guī)模問題的求解。為了進(jìn)一步驗(yàn)證所建立模型的求解規(guī)模以及求解效率，本文首先對前攝性調(diào)度模型進(jìn)行了算例測試。分別對含有不同數(shù)目的工序的項(xiàng)目，在可更新資源數(shù)目為一種和多種的情況下進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證其在可接受的時間內(nèi)能夠求解的算例規(guī)模的大小，并選取固定的參數(shù)對模型進(jìn)行多次求解實(shí)驗(yàn)，驗(yàn)證前攝性模型在求解時間方面的穩(wěn)定性。本文中提出的前攝性調(diào)度模型的代碼均采用MATLAB進(jìn)行編碼，并在計算機(jī)上運(yùn)行求解。

由于所選的測試案例均為隨機(jī)生成案例，在隨機(jī)生成過程中，需要對資源總量、各工序工期的標(biāo)準(zhǔn)差及期望值等的范圍進(jìn)行確定，在進(jìn)行案例測試時，對部分參數(shù)設(shè)置如表2所示。

表2 案例參數(shù)

首先對前攝性調(diào)度模型的最大求解規(guī)模進(jìn)行實(shí)驗(yàn)，即在資源類型分別為1、2和4種的情況下，逐步增加項(xiàng)目中所包含工序的數(shù)目，在可允許的時間范圍內(nèi)得出可求解包含的工序的最大數(shù)目。在資源類型分別為1、2和4種的情況下，設(shè)定求解時間為1 000 s，可求解的最大規(guī)模的項(xiàng)目分別為210、200、180。

在得到模型的最大求解規(guī)模之后，為了進(jìn)一步分析前攝性調(diào)度模型的穩(wěn)定性，本文分別選取了包含工序數(shù)目為30、60、90的算例進(jìn)行測試，在資源類型分別為1、2和4種的情況下，對每種情況進(jìn)行30次求解運(yùn)算，得到用分支定界算法求解不同組合情況下所需的時間，然后求出求解時間的平均值。實(shí)驗(yàn)結(jié)果如表3所示。

表3 求解時間的平均值

從表3可以看出對于含有相同工序的項(xiàng)目，平均求解時間隨可更新資源種類的增加逐漸增大，并且隨著項(xiàng)目中包含工序數(shù)目的增加，平均求解時間增加量逐漸增大。對于具有相同種類可更新資源包含不同工序數(shù)目的項(xiàng)目，平均求解時間隨工序數(shù)目的增加明顯增大。實(shí)驗(yàn)結(jié)果符合預(yù)期。

為了更加清晰全面地了解仿真實(shí)驗(yàn)的結(jié)果，根據(jù)表1中“包含工序的數(shù)目”和“可更新資源種類”的不同組合，采用分支定界算法分別進(jìn)行30次實(shí)驗(yàn)，得出結(jié)果并繪制出相應(yīng)的散點(diǎn)圖，如圖1～3所示。圖1(a)～(c)為包含30個工序，資源類型分別為1，2，4種資源的散點(diǎn)圖，圖2(a)～(c)為包含60個工序，資源類型分別為1、2、4種資源的散點(diǎn)圖，圖3(a)～(c)為包含90個工序，資源類型分別為1、2、4種資源的散點(diǎn)圖。

圖1 包含30個工序的散點(diǎn)圖

圖2 包含60個工序的散點(diǎn)圖

圖3 包含90個工序的散點(diǎn)圖

從散點(diǎn)圖可以看出，隨著可更新資源的增加，包含不同工序數(shù)量的項(xiàng)目的求解時間都隨之增大。同樣，對于具有相同種類的可更新資源的項(xiàng)目，隨著其包含的工序數(shù)目的增加求解時間也隨之增加。但是，對于具有相同工序和相同類型可更新資源的項(xiàng)目，求解時間分布較為均衡，波動起伏較小，穩(wěn)定性較高。對于只含有30個工序的項(xiàng)目，可更新資源的種類的增加對模型的求解時間的影響并不顯著，但是對于包含90個工序的項(xiàng)目而言，隨著可更新資源種類的增加，模型的求解時間增加較為明顯。

4 結(jié)束語

本文通過對帶有廣義優(yōu)先關(guān)系的資源受限項(xiàng)目調(diào)度進(jìn)行分析，在不確定環(huán)境下以工期最小化和魯棒性最大化為目標(biāo)構(gòu)建了雙目標(biāo)的前攝性資源受限項(xiàng)目調(diào)度模型，考慮到所建立模型的NP-hard性質(zhì)和前攝性項(xiàng)目調(diào)度對進(jìn)度計劃穩(wěn)定性要求的性質(zhì)，選用求解精確解的分支定界算法對模型進(jìn)行求解。為了驗(yàn)證所建立模型的有效性和穩(wěn)定性，分別對模型在可接受時間內(nèi)的最大求解規(guī)模以及針對不同規(guī)模的算例的求解的穩(wěn)定性進(jìn)行了測試。結(jié)果顯示隨著項(xiàng)目中所包含的工序的數(shù)目和可更新資源的種類的增加，模型求得精確解所需要的時間隨之增加，但是針對具有相同的工序數(shù)目和可更新資源類型的項(xiàng)目，求得精確解所需的時間的波動較小，穩(wěn)定性較高。此外，隨著項(xiàng)目中所包含工序數(shù)目的增加，可更新資源種類的多少對模型求解精確解的時間影響逐漸增大，可更新資源種類的增加會導(dǎo)致大規(guī)模項(xiàng)目求解精確解所需的時間增加較為明顯。

本文在建立模型時僅考慮了工期以及魯棒性，并未考慮加入時間緩沖造成的項(xiàng)目成本的增加以及其他不確定因素的干擾，并且模型中模型的時間緩沖的表示方式可能會導(dǎo)致部分工序的時間緩沖有所重疊，造成魯棒性指標(biāo)偏高。因此，在后續(xù)的研究中可以更進(jìn)一步研究如何合理地表示工序的時間緩沖的大小，使魯棒性指標(biāo)更加合理。