關鍵鏈項目調(diào)度中的資源分配算法研究

崔南方,陳 雪,張 艷

(華中科技大學 管理學院 湖北 武漢 430074)

為了應對外部環(huán)境和項目本身的不確定性，構建一個具有強抗干擾能力的項目調(diào)度計劃顯得非常重要，因此，魯棒性項目調(diào)度受到了廣泛關注。如DEMEULEMEESTER等[1]研究表明，魯棒性資源分配方法和關鍵鏈技術均可以有效提高項目調(diào)度的魯棒性。GOLDRATT[2]提出了關鍵鏈項目調(diào)度方法,該方法綜合考慮工序和資源約束來構建項目調(diào)度計劃，并通過插入緩沖來提高項目調(diào)度的魯棒性,目前對關鍵鏈項目調(diào)度的研究主要集中在識別關鍵鏈、計算緩沖方法等方面[3]。BIE等[4]提出了一種基于活動依賴性的緩沖區(qū)大小確定方法。ZHANG等[5-6]在考慮工序和資源約束的基礎上，進一步考慮了活動之間的信息流，以最小化總協(xié)調(diào)成本為目標來確定關鍵鏈排序，并研究了模糊資源約束下項目調(diào)度問題的緩沖計算方法。YANG等[7]提出了一種基于任務優(yōu)先級和關鍵鏈的多項目調(diào)度方法。

魯棒性資源分配的目的是找到魯棒性較好的資源傳遞路線來保護項目完工期。LEUS等[8]利用資源流網(wǎng)絡、分支定界算法對魯棒性資源分配問題進行求解。DEBLAERE等[9]以最小化項目懲罰成本為目標，提出了3種基于整數(shù)規(guī)劃的資源分配的啟發(fā)式算法和一種最小化項目懲罰成本的構建法MABO，并將這幾種算法與平行調(diào)度生成計劃和鏈式局部調(diào)度啟發(fā)式算法做了比較，結(jié)果顯示MABO算法得到的項目調(diào)度魯棒性最好。而近幾年關于資源分配算法的研究[10-11]主要關注于資源分配的算法效率，很少考慮資源分配算法的魯棒性效果。

傳統(tǒng)的關鍵鏈項目調(diào)度過程中并沒有預先確定資源在活動間如何傳遞，資源一旦釋放便可用于其他任一未完成活動。然而，實際項目的實施都會提前安排好資源(尤其是人力資源)的任務和流動。在項目開始前安排好資源，有利于決策者做好外部活動計劃，有利于員工提前知道自己未來的工作[12]，所以在關鍵鏈項目調(diào)度中考慮資源分配很有必要。李俊亭[13]綜合分析了關鍵鏈項目進度控制中的資源分配，提出了一種基于優(yōu)先規(guī)則的資源配置方案，但這種方案是響應式的，沒有在制定項目調(diào)度計劃時考慮資源分配。

基于此，筆者將魯棒性資源分配應用于關鍵鏈項目調(diào)度，提出了一種針對關鍵鏈項目調(diào)度的主動式資源分配方案來提高項目調(diào)度的魯棒性，以便使關鍵鏈調(diào)度計劃在執(zhí)行過程中能夠更好地抵御活動工期的不確定性，提高完工率。同時，通過大規(guī)模仿真實驗進一步分析了多種不同的資源分配對關鍵鏈調(diào)度計劃魯棒性的影響，驗證了算法的有效性。

1 資源分配

1.1 資源流網(wǎng)絡

定義原始項目網(wǎng)絡為G=(N,A)，N為節(jié)點集合，表示項目活動；A為箭線集合，代表活動之間的先后關系。節(jié)點集合N={0,1,2,…,n}，其中包括虛擬節(jié)點0和n。對于項目中的任意活動j，其工期為dj，對第k(k=1,2，…,K)種資源的需求量為rjk，而每種資源的可利用量為ak，其中虛擬節(jié)點0和n的工期和資源消耗量均為0。活動的實際開始時間為Sj，計劃開始時間為sj。由分支定界算法得到的基準計劃為S。

ARTIGUES等[14]最早提出資源流的概念，用來描述資源在活動之間的流動情況。資源流網(wǎng)絡G′=(N,AR)與原始項目網(wǎng)絡G=(N,A)的節(jié)點數(shù)相同，但是資源弧集合AR是連接節(jié)點i和節(jié)點j的箭線集合，且節(jié)點i和節(jié)點j之間存在任意一種資源k的資源流fijk(fijk>0)。假設每種資源k從虛擬開始活動流出的資源總量等于流入虛擬結(jié)束活動的總量，且等于該種資源的總可利用量ak，其數(shù)學表達式如式(1)所示。并且，一個可行的資源流網(wǎng)絡還必須滿足在每一個活動節(jié)點的流量守恒，即對于每種資源k和每個非虛擬活動i(i≠0,n)，流入該活動的總量必須等于流出量，且等于該活動的資源需求量rik，其數(shù)學表達式如式(2)所示。

?k∈K

(1)

?i∈N{0,n},?k∈K

(2)

1.2 魯棒性資源分配

項目調(diào)度的魯棒性分為兩類：第一類是質(zhì)魯棒性, 指整個項目的完成時間的穩(wěn)定性,用按時完工率或完工期度量；第二類是解魯棒性, 指活動開始時間的穩(wěn)定性[15]。在關鍵鏈項目調(diào)度中，多用不確定情況下的平均完工率(質(zhì)魯棒性)衡量調(diào)度計劃的魯棒性。對于同一個項目，滿足資源流網(wǎng)絡約束的資源分配方案可能有多種，筆者用一個小項目算例說明資源分配方案給項目魯棒性帶來的影響。

項目用AON網(wǎng)絡圖表示，如圖1所示，其中活動1和活動6分別為虛擬開始節(jié)點和虛擬結(jié)束節(jié)點，圓圈內(nèi)數(shù)字代表活動編號，活動上方數(shù)字為活動時間，下方數(shù)字為活動的資源需求，該項目只涉及一種可更新資源，資源總量為4個單位。

圖1 項目網(wǎng)絡圖

圖2 資源分配方案a

圖3 資源分配方案b

一種可行的資源分配方案a如圖2所示，可看出完工期為4個單位，活動3的資源有一個來自活動4，另一個來自活動2。另一種資源分配方案b，如圖3所示，可看出活動3所需的2個資源都來自活動4，完工期同樣為4個單位。方案a中，活動2或活動4延遲1個單位時間都會造成活動3不能按時開工，從而使得整個工期延長。然而在其他條件相同的情況下，方案b中，只有活動4延遲會影響活動3，而活動2延遲1個單位開始并不會影響整個工期，這種方案下的項目完工率會更加穩(wěn)定。可見，資源分配方案b的項目魯棒性比方案a更好。

至此電動汽車最優(yōu)出行的約束條件便已完成，配合聯(lián)合目標函數(shù)，共同構成了電動汽車最優(yōu)出行路徑的規(guī)劃模型。由此模型，便能求解出任意初始位置與終止位置的最優(yōu)路徑。

項目調(diào)度中考慮資源分配本身是一種NP難題，筆者將針對關鍵鏈項目調(diào)度，探索出一種具有較好魯棒性的資源分配方案。

2 基于優(yōu)先規(guī)則的主動式關鍵鏈資源分配算法

2.1 算法設計

關鍵鏈的長度決定了項目工期，所以欲使項目盡快完工則需要保證關鍵鏈順利進行。根據(jù)TOC思想，非關鍵鏈要盡可能“遷就”關鍵鏈，盡可能不讓非關鍵鏈活動的延遲影響關鍵鏈活動，即減少非關鍵鏈活動對關鍵鏈活動的資源約束?；谝陨纤枷?，筆者提出了關鍵鏈資源分配算法(critical chain resource allocation,CCRA)，該算法以關鍵鏈活動為核心，在不影響計劃最短完工期的情況下，優(yōu)先滿足關鍵鏈活動的資源需求，盡量減少非關鍵鏈活動對關鍵鏈活動的資源約束，以保證關鍵鏈順利進行，使得項目更加穩(wěn)健地執(zhí)行。算法按照活動開始時間的先后順序，依次為其分配資源，提供資源的活動為已完成的活動，且分配資源時滿足一定規(guī)則以得到魯棒性較好的資源分配方案。具體步驟如下：

(1)構建基準調(diào)度計劃并找出關鍵鏈。以最短工期為目標，使用DEMEULEMEESTER等[16]設計的分支定界算法生成項目基準調(diào)度計劃S，通過活動最早開始時間和最晚開始時間找到關鍵鏈。

(2)生成資源待分配的活動順序Sequence。首先根據(jù)基準調(diào)度計劃，按照活動最早開始時間由小到大排列所有活動，開始時間相同的活動，先安排序號較小的活動。然后在開始時間相同的活動中將關鍵鏈活動提前(為了優(yōu)先給關鍵鏈活動分配資源)，非關鍵鏈活動順序不變，從而得到最終的資源待分配順序Sequence。

(3)初始化各活動資源可供給數(shù)量，其值等于各活動資源需求。

(4)依次為Sequence中的待分配活動i找到可以為其提供資源的活動序列Supply_set(在活動i之前完成且資源供給不為零)，該序列確定了為活動i提供資源的活動先后順序，其優(yōu)先規(guī)則如下：①如果活動i是關鍵鏈活動，則優(yōu)先用其緊前的關鍵鏈活動提供資源，再用緊前的非關鍵鏈活動提供資源，最后用其他可提供資源的活動(先完成的活動優(yōu)先)提供資源；②如果活動i是非關鍵鏈活動，則優(yōu)先用其緊前的非關鍵鏈活動提供資源，再用緊前的關鍵鏈活動提供資源，最后用其他可提供資源的活動(先完成的活動優(yōu)先)提供資源。

(5)分配資源。用提供資源的活動集合Supply_set依次給當前待分配資源的活動i提供資源，更新活動i的資源需求和提供資源活動的供給數(shù)量，直到活動i的資源需求被滿足。然后，轉(zhuǎn)步驟(4)分配下一個活動，直到所有活動資源需求都被滿足。

步驟(4)中選擇先完成的活動優(yōu)先提供資源是為了保證非關鍵鏈匯入關鍵鏈的總時差，因為時差越大，魯棒性越好。另外，如果活動j要給活動i分配資源，則應盡可能多地分配資源(不超過活動i的資源需求量)，以減少額外資源約束。

2.2 算例說明

為了更直觀地說明CCRA算法，筆者以圖1的簡單項目為例演示具體資源分配步驟。

(1)得到最小完工期對應的項目基準調(diào)度計劃S=[0,0,2,0,2]。根據(jù)基準調(diào)度計劃得到關鍵鏈為1→4→3→6。

(2)根據(jù)最早開始時間和關鍵鏈活動得到資源待分配順序(不考慮虛擬活動)Sequence=[2,4,3,5]，其中活動2和活動4開始時間相同，但活動4是關鍵鏈活動，則活動4在活動2前被分配資源，得到最終活動資源分配序列Sequence=[4,2,3,5]。

(3)初始化各活動資源可供給數(shù)量，其值等于各活動資源需求。

(4)分配資源。根據(jù)Sequence首先給活動4分配資源：活動4開始時，可以提供資源的活動為Supply_set4=[1],則f1,4=3(此時，活動4資源需求變?yōu)?，活動1資源供給變?yōu)?)；接著分配活動2，Supply_set2=[1],則f1,2=1；分配活動3，Supply_set3=[4,2](此時活動4和活動2都可提供資源，但因為活動3是關鍵活動，優(yōu)先讓前序關鍵活動4提供資源),則f4,3=2(此時，活動3資源需求變?yōu)?)；分配活動5，Supply_set5=[2,4](因為活動5為非關鍵活動，優(yōu)先讓緊前非關鍵活動2提供資源),則f2,5=1；活動6為虛擬活動，需求為0，不作考慮。至此完成CCRA資源分配過程，得到資源分配結(jié)果即為圖3所示的魯棒性更好的分配方案。

對比兩種資源分配方案可以看出，相比于資源分配方案a，方案b做到了盡量“遷就”關鍵鏈，減少了2→3和4→5的兩個額外資源約束，且具體資源分配數(shù)量也有不同。

3 不同資源分配算法的對比分析

3.1 實驗設計

為了驗證筆者所提資源分配算法的有效性，筆者使用Matlab軟件進行大規(guī)模仿真實驗，選擇了PSPLIB實例集J30中具有代表性的48個項目例子進行模擬仿真，比較不同的資源分配算法對關鍵鏈項目調(diào)度計劃魯棒性的影響。對比的資源分配算法包括：隨機資源分配算法、MABO資源分配算法、筆者提出的關鍵鏈資源分配算法CCRA。隨機資源分配算法在進行資源分配時不考慮任何魯棒性績效指標，實驗中作為比較基準；MABO資源分配算法是目前資源受限型項目調(diào)度研究中能夠獲得較好魯棒性的一種資源分配算法。

實驗中關鍵鏈項目調(diào)度計劃生成的具體步驟如下：①以最短工期為目標，構建項目基準調(diào)度計劃S，找出關鍵鏈活動(使用文獻[16]提出的分支定界算法得到S，使用文獻[17]提出的方法查找關鍵鏈和非關鍵鏈)。②使用3種資源分配算法(隨機、MABO、CCRA)得到具體資源分配方案。③根據(jù)工序約束和資源約束，分別重新確定非關鍵鏈(關鍵鏈不變)。④在非關鍵鏈與關鍵鏈匯合處插入?yún)R入緩沖FB(使用剪切粘貼法，大小為50%的非關鍵鏈長度[18])，筆者不考慮項目緩沖。⑤調(diào)整緩沖大小解決二次資源沖突(斷開關鍵鏈)，輸出關鍵鏈調(diào)度計劃。⑥將生成的1 000次模擬活動時間按照3種不同的調(diào)度計劃執(zhí)行，分別統(tǒng)計魯棒性指標。

式中：wi為每個活動權重,表示該活動延遲一個時間單位開工所造成的損失；Si和Si*分別表示活動i的計劃開始時間和仿真執(zhí)行中的實際開始時間。

3.2 實驗結(jié)果分析

3種資源分配算法的仿真結(jié)果如表1所示，MABO和CCRA兩種算法相對隨機資源分配的優(yōu)化百分比統(tǒng)計如表2所示。由表1可知，隨著活動工期不確定性(σ)的增加，3種方法各自的平均懲罰成本都增加，平均按時完工率降低，平均完工時間增加。符合項目的不確定越大，越會影響項目的執(zhí)行的規(guī)律。結(jié)合表1和表2結(jié)果對比分析3種資源分配算法，在σ=0.3的水平下，平均按時完工率最高的是CCRA算法，為92.58%，優(yōu)化百分比為2.66%；在σ=0.6的水平下，CCRA算法的平均按時完工率最高，為59.55%，提高比率為9.67%；在σ=0.9的水平下，完工率依然是CCRA算法表現(xiàn)最好。隨著活動時間不確定性的增加，在按時完工率和平均完工時間方面，CCRA算法的效果一直保持最好，具有一致性。所以，就質(zhì)魯棒性而言，CCRA算法比另外兩種算法更優(yōu)。

表1 3種資源分配算法仿真結(jié)果

在解魯棒性方面，當σ=0.3時，MABO算法的平均懲罰成本低于CCRA算法，而當σ=0.6和σ=0.9時，CCRA算法的平均懲罰成本低于MABO算法。可見，雖然MABO算法的目標函數(shù)是最小化懲罰成本，但是在“接力賽”執(zhí)行策略中，效果并非一直最好。所以，就解魯棒性而言，隨著活動時間不確定性的增加，CCRA算法的表現(xiàn)也會比MABO算法好。出現(xiàn)這種結(jié)果的一種可能的解釋是，當活動不確定性較小時，活動工期波動不大，因而緩沖消耗不大，在接力賽的執(zhí)行策略下，CCRA算法的完工率高，活動基本提前完工，導致活動的實際開始時間與計劃時間偏差較大；而隨著活動時間不確定性的增大，CCRA算法在懲罰成本方面的優(yōu)勢就能體現(xiàn)出來，MABO算法因為計劃完工期延期較多，完工率低，以致懲罰成本這一指標也不如CCRA算法。

表2 算法優(yōu)化百分比 %

此外，實驗還統(tǒng)計了3種算法的平均耗時，即48個項目生成關鍵鏈調(diào)度計劃并執(zhí)行該計劃所耗平均時間(其他參數(shù)完全相同)：隨機資源分配算法的平均耗時為14.311 s，CCRA算法的平均耗時為14.765 s，而MABO算法的平均耗時為314.611 s?？梢?，CCRA算法的效率較MABO算法有顯著提高。因此，在制定項目調(diào)度計劃時，運用不同的資源分配方案確實會影響項目執(zhí)行的魯棒性，并且，優(yōu)先保證關鍵鏈上活動執(zhí)行的資源分配方案能夠有效提高項目的魯棒性。

4 結(jié)論

將項目管理領域中相對獨立的魯棒性資源分配研究和關鍵鏈項目管理研究相結(jié)合，提出了新的能有效提高關鍵鏈項目調(diào)度計劃魯棒性的資源分配方法。在傳統(tǒng)關鍵鏈項目調(diào)度過程中考慮魯棒性資源分配，通過一個算例說明了資源分配方案的不同會對項目調(diào)度魯棒性產(chǎn)生影響，進而針對關鍵鏈項目調(diào)度的特點，提出了關鍵鏈資源分配算法CCRA。CCRA算法的主要思想是優(yōu)先滿足關鍵鏈活動的資源需求，并盡量減少非關鍵鏈活動資源向關鍵鏈活動傳遞的路徑，從而減少非關鍵活動對關鍵鏈活動的影響，保護項目完工期。

通過大規(guī)模仿真實驗對比了3種不同的資源分配方法對關鍵鏈項目調(diào)度魯棒性的影響，驗證了CCRA算法的有效性。實驗結(jié)果表明：活動執(zhí)行時間不確定性(σ)越高，則項目完工率越低，懲罰成本越高；在同一活動時間不確定性水平下，CCRA算法得到的項目調(diào)度計劃質(zhì)魯棒性(完工率、完工期)最好，解魯棒性(懲罰成本)總體也優(yōu)于其他兩種算法；相比于目前效果較好的MABO資源分配算法，CCRA算法的計算效率更高?？梢?不同的資源分配方案會影響關鍵鏈項目調(diào)度的魯棒性，CCRA算法可以得到魯棒性更好的關鍵鏈項目調(diào)度計劃，更加適用于關鍵鏈項目調(diào)度。

未來有關關鍵鏈項目調(diào)度的研究，可進一步探究魯棒性資源分配對緩沖控制會產(chǎn)生何種影響，以便為項目的緩沖控制提供更多的管理方法和啟示。