集成時間緩沖與資源流的多技能項目魯棒調度方法

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

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

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

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

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

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

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

此外,時間緩沖與資源流調整之間存在交互影響,這是現有魯棒項目調度研究領域少有涉及的。基于此,本文構建了多技能項目魯棒調度問題優化模型,并深入剖析了時間緩沖與資源流調整之間的交互影響機制;提出了集成時間緩沖與資源流調整的多技能項目魯棒調度算法,對一個單項目案例和一個項目案例庫進行了大規模仿真實驗以檢驗算法的性能。最后,本文總結了研究內容并提出了下一步的研究方向。

1 問題建模及分析

1.1 問題描述與建模

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

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

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

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

1.2 時間緩沖與資源流調整的交互影響分析

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

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

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

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

圖2 調度計劃的魯棒優化Fig.2 Robust optimization of scheduling plan

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

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

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

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

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

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

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

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

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

2.2 資源流魯棒優化算法

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

資源流魯棒優化的本質在于改變活動間的先后約束關系,使調度計劃中的活動約束更利于其保持穩定性,因此,不能改變活動約束的資源流調整是無意義的。基于此,首先分析調度計劃中活動約束的類型。

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

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

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

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

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

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

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

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

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

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

2.3 緩沖回退過程

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

3 實驗設計及結果分析

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

3.1 單項目案例實驗

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

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

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

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

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

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

3.2 項目案例集實驗

3.2.1 實驗設計 在實驗對象方面,采用Wang等[17]所設計的多技能項目案例集,選擇其中的360個項目案例,每個項目案例包含32個活動。項目特征參數有3個:網絡復雜度(NC)、需求因素(RF)和技能水平(SL),參數含義參考 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種不同的參數組合,每個參數組合下包含10個項目案例。項目中活動的邊際進度偏離成本由[0,10]隨機生成,即ci∈[0,10],結束節點的邊際進度偏離成本,也表示項目的邊際逾期成本。

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

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

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

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

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

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

4 結語

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

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

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

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

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

附錄A

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

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

其逆否命題為:

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

命題2的證明

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

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

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

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

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

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

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

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

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