集成時(shí)間緩沖與資源流的多技能項(xiàng)目魯棒調(diào)度方法

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

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

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

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

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

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

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

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

1 問題建模及分析

1.1 問題描述與建模

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 基于Monte-Carlo模擬的風(fēng)險(xiǎn)評估

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 緩沖回退過程

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

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

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

3.1 單項(xiàng)目案例實(shí)驗(yàn)

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

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

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

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

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

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

3.2 項(xiàng)目案例集實(shí)驗(yàn)

3.2.1 實(shí)驗(yàn)設(shè)計(jì) 在實(shí)驗(yàn)對象方面,采用Wang等[17]所設(shè)計(jì)的多技能項(xiàng)目案例集,選擇其中的360個(gè)項(xiàng)目案例,每個(gè)項(xiàng)目案例包含32個(gè)活動(dòng)。項(xiàng)目特征參數(shù)有3個(gè):網(wǎng)絡(luò)復(fù)雜度(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ù)組合,每個(gè)參數(shù)組合下包含10個(gè)項(xiàng)目案例。項(xiàng)目中活動(dòng)的邊際進(jìn)度偏離成本由[0,10]隨機(jī)生成,即ci∈[0,10],結(jié)束節(jié)點(diǎn)的邊際進(jìn)度偏離成本,也表示項(xiàng)目的邊際逾期成本。

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

附錄A

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

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

其逆否命題為:

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

命題2的證明

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

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

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

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

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

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

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

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

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