胡振濤 ,崔南方 ,胡雪君 ,張 艷

(1.華中科技大學 管理學院,武漢 430074;2.湖南大學 工商管理學院,長沙 410082;3.東莞理工學院 經(jīng)濟與管理學院,廣東 東莞 523808)

資源受限項目調(diào)度問題(Resource Constrained Project Scheduling Problem,RCPSP)主要研究內(nèi)容是:在項目的活動及資源等約束下求解一個符合目標的調(diào)度計劃,作為項目實施期進度安排的依據(jù)。其中,最常見的優(yōu)化目標有工期[1]、成本[2]、凈現(xiàn)值[3]和資源均衡[4]等。多技能項目調(diào)度問題(Multi-Skilled Project Scheduling Problem,MSPSP)是RCPSP 的一種,與傳統(tǒng)RCPSP 不同的是,其中的資源具備多技能,可以在不同活動中承擔不同的任務,因此,其資源分配方式更加靈活,解空間更大,求解難度也更高[5]。

然而,在項目實施過程中存在不確定因素,這些不確定因素可能會使項目中某些預設的參數(shù)發(fā)生變化,進一步導致項目的實際進度與調(diào)度計劃之間產(chǎn)生偏差。這種進度上的偏離往往伴隨著額外的成本,如財務成本、庫存成本、組織協(xié)調(diào)成本等[6],為應對這一問題,學者們提出了魯棒項目調(diào)度方法。

作為最有效也是成本最低的魯棒項目調(diào)度方法之一,預應式魯棒調(diào)度一直以來受到學者的廣泛關注。其核心思想是在項目計劃期便考慮項目實施期的不確定性,并在調(diào)度計劃中加入魯棒性措施,以生成一個具備抗干擾能力的調(diào)度計劃。該調(diào)度計劃應滿足以下兩點:①符合項目的一切約束;②當實施該調(diào)度計劃時,即便發(fā)生隨機事件的干擾,也具備一定的保持進度不變的能力。

預應式魯棒調(diào)度主要從時間和資源兩個方面對調(diào)度計劃進行優(yōu)化?；跁r間的魯棒調(diào)度方法通過主動推遲調(diào)度計劃中活動的開始時間,為其設置時間緩沖,為可能發(fā)生的不確定事件預留時間,其研究重點是緩沖位置和大小的計算。根據(jù)目標函數(shù)的不同,緩沖的設置方法也不同。Goldratt[7]結(jié)合約束理論和魯棒項目調(diào)度提出了關鍵鏈緩沖管理(Critical Chain Buffer Management,CC/BM),向調(diào)度計劃中插入時間緩沖以起到吸收不確定因素干擾的目的。劉士新等[8]根據(jù)緩沖在調(diào)度計劃中位置的不同將之分為項目緩沖和接駁緩沖。緩沖大小的計算方式有剪貼-粘貼法和根方差法等[9-10]。然而,這種集中式的緩沖管理方法往往只考慮項目或活動延遲概率的大小,很少關注延遲所引起的損失情況。為此,有學者提出了分散式緩沖管理方法,如基于活動開始時間關鍵度(Starting Time Criticality,STC)的時間緩沖設置方法[11],綜合考慮了活動的延期風險及活動的延遲損失,將時間緩沖分散地設置在項目各個活動前。然而,現(xiàn)有的集中式和分散式的時間緩沖管理方法都存在風險估計不準確、緩沖設置方式不合理等不足。

在資源方面,主要是針對資源流的魯棒優(yōu)化,所謂資源流指的是資源在活動間的傳遞[12]。活動之間會因為共用資源而產(chǎn)生先后約束,通過調(diào)整資源流改變活動間的約束關系便是基于資源的魯棒調(diào)度方法的主要研究內(nèi)容。Deblaere等[13]提出基于活動的短視優(yōu)化法,優(yōu)先從活動的緊前活動選擇資源。梁洋洋等[3]從凈現(xiàn)值的角度,以最小化懲罰成本為目標提出了資源流網(wǎng)絡的優(yōu)化算法。在多技能項目中,多技能資源的特性使活動間的資源流更加靈活多變,對資源流魯棒優(yōu)化方法也有更高的要求。然而,現(xiàn)有基于資源的魯棒調(diào)度研究多是針對單技能資源,缺乏對多技能資源的關注。

此外,時間緩沖與資源流調(diào)整之間存在交互影響,這是現(xiàn)有魯棒項目調(diào)度研究領域少有涉及的?；诖?本文構(gòu)建了多技能項目魯棒調(diào)度問題優(yōu)化模型,并深入剖析了時間緩沖與資源流調(diào)整之間的交互影響機制;提出了集成時間緩沖與資源流調(diào)整的多技能項目魯棒調(diào)度算法,對一個單項目案例和一個項目案例庫進行了大規(guī)模仿真實驗以檢驗算法的性能。最后,本文總結(jié)了研究內(nèi)容并提出了下一步的研究方向。

1 問題建模及分析

1.1 問題描述與建模

項目網(wǎng)絡采用節(jié)點式表示,共包含n個活動節(jié)點,其中:起始節(jié)點1和終止節(jié)點n表示虛活動;活動之間存在工序約束。G=(V,E)表示項目網(wǎng)絡,其中:V={1,2,…,i,j,…,n}為活動集合;E為有向弧,表示活動的工序約束。Pi為與活動i有先后約束關系的前序活動的集合;活動i的時間為隨機變量,其期望值為di。R={1,2,…,k,…,K}為項目中的資源集合,資源總數(shù)量為K。項目涉及L種技能,以F={1,2,…,l,…,L}表示。資源具備多技能,當資源k具備技能l時,RFkl=1;否則,RFkl=0?；顒觟對技能l的需求量用TFil表示。

本文研究在活動時間不確定的環(huán)境下,以最小化項目進度偏離成本為目標,多技能項目的魯棒調(diào)度方法。其前提條件是已有一個可行的基準調(diào)度計劃,通過對該調(diào)度計劃進行時間和資源上的調(diào)整以達到提高其魯棒性降低項目進度偏離成本的目的。多技能項目基準調(diào)度計劃的制定已有較多的研究成果,如基于優(yōu)先規(guī)則的并行調(diào)度[14]、遺傳規(guī)劃算法[15]以及基于動態(tài)資源權(quán)重的啟發(fā)式算法[1]等。STb表示基準調(diào)度計劃中各活動的開始時間,其中活動i的開始時間為。xb表示基準調(diào)度計劃中的資源分配方案,其中表示資源k以技能l的形式被指派到活動i中。向STb中插入時間緩沖的過程即為基于時間的魯棒優(yōu)化過程,STr表示經(jīng)過魯棒優(yōu)化后各活動的開始時間。調(diào)整xb的過程即為基于資源的魯棒優(yōu)化過程,xr表示經(jīng)過魯棒優(yōu)化后的資源分配方案。

在不確定環(huán)境下,項目有一個截止工期,超過的調(diào)度計劃是不被接受的,即在向STb中插入緩沖時調(diào)度計劃的最長工期為。由于不確定因素的存在,在項目實施期活動的實際時間可能與其期望值不同,以di表示?；顒拥膶嶋H開始時間也不一定完全符合調(diào)度計劃,以STi表示。項目活動的實際進度偏離調(diào)度計劃時會產(chǎn)生重調(diào)度成本、額外庫存成本等,項目實際工期超過會產(chǎn)生逾期成本。以ci表示活動i的邊際進度偏離成本,其中cn為項目逾期成本。本文所研究的問題以最小化項目進度偏離成本為目標構(gòu)建模型,即:

其中,式(1)表示目標函數(shù),TDC表示整個項目的總進度偏離成本。在項目實施過程中,活動存在3種類型的進度偏離:開始時間偏離、持續(xù)時間偏離和結(jié)束時間偏離。其中,活動開始時間偏離會帶來額外的物料庫存成本、計劃調(diào)整成本等。活動持續(xù)時間偏離為外生變量,不受系統(tǒng)影響且無法通過調(diào)度手段改變,因此不予考慮。而結(jié)束時間偏離所造成的影響一般可轉(zhuǎn)化為其對后續(xù)活動開始時間上的影響。因此,本文所考慮的進度偏離成本中活動的偏離量以開始時間偏離量表示。式(2)表示項目的調(diào)度計劃不可違背活動的先后關系約束。式(3)表示調(diào)度計劃的工期不可超過項目截止工期。式(4)表示必須滿足活動對技能的需求。式(5)中表示調(diào)度計劃中在時刻t時活動i的狀態(tài),其中t表示時間。當1時,表示活動i在時刻t處于進行中;當0時,表示活動i在時刻t未開始或已完工。式(6)表示在任意時刻t,對于任意的資源k而言,使用它的活動不可多于一個,即限制了資源沖突。式(7)表示決策變量的可行域。

1.2 時間緩沖與資源流調(diào)整的交互影響分析

首先引入項目案例(I),其項目網(wǎng)絡及相關參數(shù)如圖1(a)所示,如活動2的活動時間為1天,需要1單位技能F1、0單位F2及0單位F3。其中,有向?qū)嵕€表示活動的先后關系約束,虛線為圖1(c)這一調(diào)度計劃所對應的資源流。圖1(b)為該項目的資源-技能情況。項目內(nèi)共有3個資源3種技能,其中,資源R2為多技能資源,同時具備技能F1和F2。圖1(c)為該項目一個工期最短的基準調(diào)度計劃的甘特圖。其中:橫軸表示時間,縱軸表示資源;矩形中的數(shù)字表示對應的活動編號;括弧內(nèi)表示對應資源在活動中所使用的技能,如資源R2在活動2中使用了技能F1;點線表示項目的截止工期,即9。

圖1 項目案例(I)Fig.1 Project instance (I)

圖1(d)是實施圖1(c)中調(diào)度計劃時一個可能的實際進度,其中,陰影部分表示相應活動在實際進度中超出期望值的部分,如活動2 的期望時間為1天,因為不確定因素拖期了1天,實際時間為2天。由圖1(d)可以看出,由于活動2的拖期,活動3的開始時間被推遲了1 天,即當1,d2=2時,ST3=2,活動3的進度和計劃之間出現(xiàn)了偏差。由項目網(wǎng)絡圖可知,活動2和3之間不存在工序上的約束關系,兩者存在先后約束的原因在于共用同一資源R2。同理,活動8和6之間也是相同的情況。

為了減少進度偏離,圖2(a)展示了一個插入時間緩沖后的調(diào)度計劃,各活動開始時間為STr,其中,黑色矩形表示活動前的時間緩沖。對比圖2(a)和圖1(d)可知,在設置時間緩沖后,即便活動2出現(xiàn)拖期,活動3 也會依照調(diào)度計劃開始,即當2,d2=2時,ST3=2。這便是時間緩沖對調(diào)度計劃魯棒性的影響機制。

圖2 調(diào)度計劃的魯棒優(yōu)化Fig.2 Robust optimization of scheduling plan

在資源流調(diào)整方面,由圖2(c)可以看出,活動6和7原本使用的資源R2被替換為R3,這使得活動8和6之間不再有先后約束關系。對比圖2(c)和圖1(d)可知,當活動8拖期時,活動6將不會隨之延期。這便是資源流對調(diào)度計劃魯棒性的影響機制。

傳統(tǒng)的魯棒項目調(diào)度方法將時間緩沖與資源流調(diào)整視為提高調(diào)度計劃的兩個方面,而未考慮兩者的交互影響。圖2(b)展示了先設置時間緩沖后調(diào)整資源的調(diào)度計劃。由圖2(b)可以看出,當活動2和4交換所使用的資源后,時間緩沖的情況發(fā)生了變化,活動3前的緩沖量減少,而活動5前的緩沖增加。這表明,資源流調(diào)整會影響時間緩沖的大小。進一步,圖2(d)展示了先調(diào)整資源后設置時間緩沖的調(diào)度計劃。由圖2(d)可以看出,由于在調(diào)整資源時調(diào)度計劃中沒有足夠的時間,導致活動2和4之間不能交換資源。而活動2和4之間通過交換資源可以刪除活動2和3之間的約束,可能會提高調(diào)度計劃的魯棒性。這表明,時間緩沖會影響資源流調(diào)整的范圍。

綜上所述,時間緩沖與資源流調(diào)整之間存在交互影響,在對調(diào)度計劃進行魯棒優(yōu)化時,如果將兩者分開進行,最終調(diào)度計劃可能會存在不合理的部分,如圖2(b)中時間緩沖被侵蝕,圖2(d)中部分需調(diào)整的資源未調(diào)整?；诖?本文設計了集成時間緩沖與資源流的魯棒調(diào)度方法。

2 集成時間緩沖與資源流的魯棒調(diào)度算法設計

通過前文分析可以看出,分階段的魯棒調(diào)度方法存在如下缺陷:①調(diào)整資源流時會改變活動前時間緩沖的大小,導致某些活動前產(chǎn)生過多緩沖,而另一些更需要緩沖的活動前緩沖卻被侵蝕;②設置時間緩沖后活動間會產(chǎn)生更多的空閑時間,這為資源流提供了更多的調(diào)整空間,而階段式的魯棒調(diào)度方法并不能有效利用這部分優(yōu)勢。

基于此,設計了迭代交互式的魯棒調(diào)度方法,每次向調(diào)度計劃中插入1單位的時間緩沖,而后進行資源流調(diào)整,這能有效利用時間緩沖所帶來的調(diào)整空間,避免了上述第2個缺陷。此外,為避免第1個缺陷,設計了緩沖回退機制,每次資源流調(diào)整結(jié)束后,便重新評估調(diào)度計劃,將活動前過多的緩沖回退。而由于整個算法是迭代交互進行的,緩沖被侵蝕的活動會在后續(xù)迭代過程中再次被設置緩沖。這種迭代交互式的魯棒調(diào)度方法在求解過程中通過不斷評估更新后的調(diào)度計劃指導下一次魯棒優(yōu)化過程,綜合考慮了時間緩沖和資源流對調(diào)度計劃魯棒性的影響,也包括兩者間的交互影響。算法偽代碼如下所示:

2.1 基于Monte-Carlo模擬的風險評估

算法1第2行采用了Monte-Carlo模擬方法評估調(diào)度計劃的魯棒性,相較于傳統(tǒng)的評估方法,Monte-Carlo模擬能更準確、更真實地反映項目各活動的延期情況及進度偏離成本。以Nsim表示評估時的模擬次數(shù),則

式中,為第y次模擬中活動i的實際開始時間?？梢?通過Monte-Carlo可以直接評估調(diào)度計劃所對應的期望進度偏離成本。根據(jù)大數(shù)定律可知,隨著模擬次數(shù)Nsim的增大,E(DCi)會越來越接近活動進度偏離成本的真實值,這也為更準確地設置魯棒優(yōu)化措施奠定了基礎。

2.2 資源流魯棒優(yōu)化算法

2.2.1 資源流與活動約束分析 在算法1 第11行,需要對插入緩沖后調(diào)度計劃進行資源流魯棒優(yōu)化。首先引入資源弧的概念以描述一個資源在兩個活動間流動,用表示,如圖1(a)中R2在活動2和3之間的流動可用表示。由前文分析可知,資源流之所以能影響調(diào)度計劃魯棒性,其原因在于,由于資源的排他性導致使用同一資源的活動間會產(chǎn)生先后約束。用Ei,j表示活動i、j之間的先后約束,則可描述為導致了E2,3。

資源流魯棒優(yōu)化的本質(zhì)在于改變活動間的先后約束關系,使調(diào)度計劃中的活動約束更利于其保持穩(wěn)定性,因此,不能改變活動約束的資源流調(diào)整是無意義的?；诖?首先分析調(diào)度計劃中活動約束的類型。

根據(jù)活動間約束關系的強弱,將其分為3類:第1類為工序約束,即由于工藝流程等原因造成活動間的先后約束,表現(xiàn)在圖1(a)中為有向?qū)嵕€,如E2,5。這一類約束不受調(diào)度計劃的影響,屬于項目全程均不可變動的強約束。第2類為受資源限制不可避免的約束,由于資源數(shù)量或技能需求等原因,活動間會存在一類非工序卻不可避免的約束,如項目案例(I)中的活動6和7,兩者并不存在工序約束,但是兩者的進行都需要技能F3,而項目中具備技能F3的資源只有R3,這導致活動6和7之間必然會因為R3的流動而產(chǎn)生先后約束,但是其約束既可以是E6,7也可以是E7,6。因此,這類約束屬于次強約束。第3類是由調(diào)度計劃引起的可變更的約束,這類約束隨調(diào)度計劃的不同而變動,屬于弱約束,如圖2(a)調(diào)度計劃中由所引起的E2,3,在圖2(b)調(diào)度計劃中便不再存在。

2.2.2 資源流魯棒優(yōu)化策略分析 資源流的調(diào)整實際上是活動所使用資源之間的互換,隨之產(chǎn)生的是活動約束的變更。以圖2(a)中活動2 和活動4為例,在調(diào)整資源前,由資源弧和A14,5 導致了約束E2,3和E4,5;而在圖2(b)中互換了活動2和4所使用的資源,原有約束被刪除,產(chǎn)生了新約束E4,3和E2,5。

毋庸置疑的是,活動間約束越少,調(diào)度計劃的魯棒性越強。然而,第1和第2類約束都是不可刪減的約束,因此,資源流魯棒優(yōu)化的主要對象是第3類約束?；谶@一點,本文設計資源流魯棒優(yōu)化的根本邏輯有兩點:一是盡量減少第3類約束的數(shù)量;二是如果無法減少數(shù)量,則盡量保留魯棒性更高的約束。

項目中每個活動所需要的資源數(shù)量是固定的,這就導致項目中資源弧的總數(shù)是固定的,因此要通過調(diào)整資源流來減少第3類活動約束的數(shù)量,就需要讓資源弧盡可能多地與第1和第2類約束重合。以圖2(a)中活動8和6為例,由資源弧導致了第3類約束E8,6;而在圖2(b)中,通過調(diào)整資源流產(chǎn)生了新的資源弧,從而刪除了活動約束E8,6而新增了E5,6,而E5,6是本就存在的第1類約束。因此,可以說,通過調(diào)整活動6上的資源弧,刪除了約束E8,6而未新增任何約束,這無疑會提高調(diào)度計劃的魯棒性。

當調(diào)整資源流無法減少活動約束的數(shù)量時,需要評估調(diào)整前后活動約束的魯棒性。如圖2(a)和2(b)中活動2和4資源的調(diào)整,調(diào)整前的活動約束為E2,3和E4,5,調(diào)整后的約束為E4,3和E2,5,其中E2,5為第1類約束,不予考慮,則需要解決的問題是使用E4,3替換E2,3和E4,5能否提高調(diào)度計劃的魯棒性。誠然,可以通過Monte-Carlo模擬方法較為準確地評估調(diào)整前后調(diào)度計劃的魯棒性。然而,由于算法的每次迭代內(nèi)都會存在很多可調(diào)整的資源,若一概使用Monte-Carlo模擬來進行對比,無疑會大大增加算法的運行時間?；诖?借鑒Van de Vonder等[11]關于活動關鍵度的設置,以此來評估調(diào)整前后調(diào)度計劃魯棒性的變化。計算方式為

2.2.3 資源流魯棒優(yōu)化算法流程 基于上述分析,設計了資源流魯棒優(yōu)化算法,其偽代碼如下所示:

在算法2第7行,需要判斷交換后的資源能否滿足所交換活動的技能需求。在傳統(tǒng)的單技能項目中,這種判斷是簡單直接的,只需要對比所交換的資源兩者是否是同類資源即可。然而,在多技能項目中,并不能通過簡單對比得出結(jié)論。這是由于資源具備多技能,即便交換的兩者不是同類資源,也可能會存在以下情況:通過調(diào)整其他資源在活動中擔任的技能,使交換后的資源組合能滿足活動的技能需求。也即,兩個資源能否交換,不僅取決于其自身的技能稟賦,還受到對應活動中其他資源的影響。由此,這一問題轉(zhuǎn)化為:交換后各自活動所使用的資源組合能否滿足相應活動的技能需求。設交換后活動i的資源組合為Ri,由于在同一時刻每個資源只能被使用一次,盡管資源具備多技能,這些技能也是互斥的,故有以下約束:

以xkli為未知數(shù),只需要判斷方程組式(10)～(12)是否有解,即可判斷當前資源組合Ri能否滿足活動i的技能需求。然而,進一步分析可以看出,方程組式(10)～(12)是0-1型線性整數(shù)規(guī)劃問題,屬于NP難問題,一定規(guī)模時難以求解。針對該問題,提出以下技能歸并法予以解決。

2.2.4 技能歸并法 技能歸并法首先將Ri的技能視作技能供給,將活動i的需求視作技能需求,通過對不同數(shù)量的技能合并,對比供給與需求的大小。若在任意組合下供給均不小于需求,則Ri可滿足活動i,以FSB=1表示;否則,FSB=0。算法偽代碼如下所示:

算法3第3行列出了要歸并的z個技能的所有組合,第5～第9行檢驗歸并后的技能能否被當前資源滿足,其中,SUPPLYz和DEMANDz分別為技能歸并后的資源供給數(shù)量和活動需求數(shù)量。在檢驗過程中,一旦出現(xiàn)供給數(shù)量不足,則立刻跳出所有循環(huán),FSB=0;若能通過所有組合的檢驗,則FSB=1。

2.3 緩沖回退過程

為解決資源調(diào)整后的緩沖效用變化問題,設計了緩沖回退過程。在每次資源流調(diào)整后,判斷各活動前的緩沖量,若活動前存在緩沖,則減少其1單位的緩沖,并評估新調(diào)度計劃的期望進度偏離成本;若能降低成本,則接受該次回退。算法偽代碼如下所示:

3 實驗設計及結(jié)果分析

為驗證本文提出的算法,設計了單項目案例實驗和項目案例集實驗。相關程序使用Matlab R2017a編寫,測試平臺為Windows 10 操作系統(tǒng),處理器為Intel(R) Core (TM)i7-6700 CPU @3.40 GHz。

3.1 單項目案例實驗

3.1.1 實驗設計 為了分析集成式魯棒項目調(diào)度與傳統(tǒng)魯棒項目調(diào)度的不同,以前文中的項目案例(I)為實驗對象,項目的截止工期9,各活動的邊際進度偏離成本為{0,2,2,1,0.5,1,2,2,10},活動時間服從均值為di、標準差為σ的對數(shù)正態(tài)分布,考慮了低、中、高3種不確定程度,相應地,σ∈{0.3,0.6,0.9}。在算法參數(shù)方面,風險評估時的模擬次數(shù)Nsim=1 000;在仿真模擬方面,對每個環(huán)境下的調(diào)度計劃進行10萬次模擬,以保證結(jié)果的置信度。

3.1.2 結(jié)果分析 表1列出了基準調(diào)度計劃(BS)、先插入時間緩沖后調(diào)整資源流的調(diào)度計劃(BR)、先調(diào)整資源流后插入時間緩沖的調(diào)度計劃(RB)以及采用集成式魯棒優(yōu)化算法求解調(diào)度計劃(IBR)在不同不確定程度下仿真模擬的進度偏離成本。

表1 不同不確定水平下各調(diào)度計劃的總期望進度偏離成本Tab.1 Total expected deviation costs under different levels of uncertainty

由表1可見,在不同不確定程度下,集成式的魯棒優(yōu)化算法都優(yōu)于其他算法。為展示算法的優(yōu)化過程,圖3展示了隨著算法運行調(diào)度計劃的變化情況。

圖3 集成時間緩沖與資源流的魯棒優(yōu)化過程Fig.3 Robust optimization process of integrating time buffers with resource flow

其中,圖3(a)～3(b)為活動5插入緩沖,圖3(b)～3(c)調(diào)整活動6和7的資源流,圖3(c)～3(d)為活動3插入緩沖,圖3(d)～3(e)調(diào)整活動2和4的資源流,圖3(e)～3(f)回退活動5前1單位的緩沖,剩余均為插入緩沖。由調(diào)度計劃的變化過程可以看出,算法在優(yōu)化過程中能根據(jù)時間緩沖與資源流的交互影響不斷調(diào)整緩沖大小和資源流向,明顯優(yōu)于圖2中分階段式的魯棒優(yōu)化方法。

3.2 項目案例集實驗

3.2.1 實驗設計 在實驗對象方面,采用Wang等[17]所設計的多技能項目案例集,選擇其中的360個項目案例,每個項目案例包含32個活動。項目特征參數(shù)有3個:網(wǎng)絡復雜度(NC)、需求因素(RF)和技能水平(SL),參數(shù)含義參考 Wang 等[17]和Correia等[5]的研究。其中:NC∈{1.5,1.8,2.1},RF∈{0.25,0.5,0.75,1.0},SL∈{0.4,0.6,0.8}。因此,共有36種不同的參數(shù)組合,每個參數(shù)組合下包含10個項目案例。項目中活動的邊際進度偏離成本由[0,10]隨機生成,即ci∈[0,10],結(jié)束節(jié)點的邊際進度偏離成本,也表示項目的邊際逾期成本。

為對比算法在不同環(huán)境下的表現(xiàn),考慮了項目的工期寬松度及活動的不確定程度。用項目的截止日期與基準調(diào)度計劃項目工期的比值作為衡量工期寬松度的指標 即為基準調(diào)度計劃中結(jié)束節(jié)點活動n的開始時間,它等于基準調(diào)度計劃的項目工期。工期寬松度分為低、中、高3檔,τ∈{1.1,1.3,1.5}。項目的活動時間服從對數(shù)正態(tài)分布,其均值等于項目案例庫的預置時間,不確定程度用分布函數(shù)的標準差衡量,也分為低、中、高3檔,σ∈{0.3,0.6,0.9}。

在算法方面,基準調(diào)度計劃的獲取參考胡振濤等[1]的研究,魯棒優(yōu)化算法對比了先插入時間緩沖后調(diào)整資源流(BR)、先調(diào)整資源流后插入時間緩沖(RB)以及本文所提出的集成式魯棒優(yōu)化算法(IBR),其中,本文算法中風險評估時的模擬次數(shù)Nsim=1 000。在仿真模擬方面,對每個環(huán)境下的調(diào)度計劃進行10萬次模擬。

3.2.2 結(jié)果分析 表2列出了360個項目案例在不同工期寬松度和不確定程度下,通過不同算法所求解的調(diào)度計劃,最后仿真得到的平均進度偏離成本。首先分析不確定程度對項目進度的影響?？梢钥闯?隨著不確定程度的增大,無論以何種算法求解,項目的進度偏離成本都在增大。這是因為不確定風險水平越高,項目的活動時間隨機性也就越大,對調(diào)度計劃的干擾也更強,即便魯棒優(yōu)化策略也不能完全抵消這種干擾。其次分析工期寬松度的影響。隨著工期變寬松,調(diào)度計劃中可設置的時間緩沖量增多,資源流調(diào)整的空間也隨之增大,項目魯棒性增強,進度偏離成本降低。最后分析不同算法的求解性能。兩種分階段的魯棒優(yōu)化方法并無明顯差別,相較之下,本文所設計的集成時間緩沖和資源流的魯棒調(diào)度算法具有明顯優(yōu)勢,且在任何工期寬松度和不確定程度下均優(yōu)于分階段的算法。

表2 不同工期寬松度及不確定程度下各算法求解的期望進度偏離成本Tab.2 Expected deviation costs under different slacks and uncertainties solved by different algorithms

為分析在不同類型項目中算法的表現(xiàn),圖4統(tǒng)計了在τ=1.3,σ=0.6時各項目參數(shù)下算法求解的平均進度偏離成本。首先分析NC,當NC較小時,表示項目網(wǎng)絡復雜度低,活動間的約束較少,項目的魯棒性相對較高,故其對應的進度偏離成本更低,集成式魯棒調(diào)度算法相較于其他算法的優(yōu)勢比較平均。接著分析RF,它表示活動對資源的需求程度,當RF=0.25時,表示每個活動僅需要1種技能,活動間因資源而產(chǎn)生的約束較少,魯棒優(yōu)化空間小,因此,集成式算法的優(yōu)勢相對較小?？梢钥闯?當RF增大時,集成式算法的優(yōu)勢也隨之增大。最后分析SL,它表示資源平均具備的技能數(shù)量,當SL增大時,集成式算法的優(yōu)勢明顯增大。這是因為隨著資源技能的增多,資源的柔性更強,資源流調(diào)整的靈活性更大,集成式的魯棒優(yōu)化算法能綜合考慮時間緩沖與資源流的影響,從而在更大程度上提高調(diào)度計劃的魯棒性。

圖4 不同參數(shù)下用不同算法計算的平均偏差成本Fig.4 Average deviation costs of projects with different parameters solved by different algorithms

4 結(jié)語

本文研究了不確定環(huán)境下多技能項目的魯棒調(diào)度方法,以最小化項目的進度偏離成本為目標,在分析了基于時間和基于資源的魯棒優(yōu)化方法以及兩者交互作用的基礎上,提出了集成時間緩沖和資源流的迭代交互式魯棒調(diào)度算法。主要貢獻有:

(1) 深入剖析了時間緩沖與資源流對調(diào)度計劃魯棒性的影響機制以及兩者的交互作用,并在此基礎上提出了集成時間緩沖和資源流多技能項目魯棒調(diào)度算法。

(2) 分析了項目中資源流與活動約束的關系以及活動約束的類型,并在此基礎上提出了資源流魯棒優(yōu)化策略。

(3) 根據(jù)多技能資源的特點,設計了技能歸并法以判斷資源能否滿足活動的技能需求。一般情況下,相較于其他算法,技能歸并法的求解時間更短。

對單項目案例和案例集的實驗結(jié)果證明了本文所設計算法的有效性。相較于傳統(tǒng)的分階段考慮時間與資源的魯棒優(yōu)化策略,集成式的魯棒優(yōu)化算法具有明顯優(yōu)勢。下一步的研究將關注更復雜不確定環(huán)境下的多技能項目魯棒調(diào)度方法。

附錄A

技能歸并法的合理性證明首先,算法來源于以下命題:

命題1若歸并任意數(shù)量任意組合的技能后,Ri對所歸并技能的供給數(shù)量,都不少于i對所歸并技能的需求數(shù)量,則至少存在一個資源分配方案,使得i內(nèi)的所有技能需求能被Ri滿足。

其逆否命題為:

命題2若對i,資源Ri不存在可行的分配方案,則至少存在一個歸并的技能組合,使得Ri對所歸并技能的供給數(shù)量少于i對所歸并技能的需求數(shù)量,即使得SUPPLY

命題2的證明

證明針對活動i,資源Ri不存在可行的分配方案有3種情況:

(1) 資源的總數(shù)量不足,即

可以看出,式(A1)不等號左側(cè)的值為資源可用總數(shù)量,它等于歸并所有技能(即z=L)為一個技能后,資源對所歸并技能的供給數(shù)量SUPPLY。同理,不等號右側(cè)等于歸并L個技能后,活動對所歸并技能的需求DEMAND。因此,式(A1)等價于SUPPLY

(2) 可用資源的總數(shù)量足夠,但是在某一個或某幾個技能上的數(shù)量不足,即

可以看出,式(A2)不等號左側(cè)的值等于歸并單個技能(即z=1)為一個技能后,資源對所歸并技能的供給數(shù)量SUPPLY。同理,不等號右側(cè)等于歸并單個技能后活動的需求DEMAND。因此,式(A2)等價于SUPPLY

(3) 可用資源的總數(shù)量足夠,在每單個技能上的資源數(shù)量也足夠,但是不存在可行的資源分配方案使得每一個技能需求被同時滿足。出現(xiàn)這種情況的原因是資源技能的排他性,即一個資源雖然同時具備多項技能,但同一時刻它只能執(zhí)行一個技能,而不能分身。因此,此時i不可行的原因是技能之間存在搶奪資源的情況。

分析兩個技能間搶奪資源的現(xiàn)象,設為技能l和m。首先,從Ri中選出具備技能l而不具備技能m的資源Rl,具備技能m而不具備技能l的資源Rm,以及同時具備技能l和m的資源Rlm。將Rl全部分配給技能l的需求,將Rm全部分配給技能m的需求,技能l和m的需求至少仍有一個未得到滿足,且剩余可分配的資源Rlm無論在兩者間如何分配,都不能使兩者被同時滿足,即兩個技能需求的差額之和大于Rlm的數(shù)量,故有

可以看出,式(A4)不等號左側(cè)的值等于歸并l和m為一個技能,資源對所歸并技能的供給數(shù)量SUPPLY。同理,不等號右側(cè)等于歸并l和m后活動的需求DEMAND。因此,式(A4)等價于SUPPLY

綜合上述3種情況以及式(A1)～(A4),命題2得證,作為其逆否命題,命題1得證。