崔南方,陳 雪,張 艷
(華中科技大學(xué) 管理學(xué)院 湖北 武漢 430074)
為了應(yīng)對(duì)外部環(huán)境和項(xiàng)目本身的不確定性,構(gòu)建一個(gè)具有強(qiáng)抗干擾能力的項(xiàng)目調(diào)度計(jì)劃顯得非常重要,因此,魯棒性項(xiàng)目調(diào)度受到了廣泛關(guān)注。如DEMEULEMEESTER等[1]研究表明,魯棒性資源分配方法和關(guān)鍵鏈技術(shù)均可以有效提高項(xiàng)目調(diào)度的魯棒性。GOLDRATT[2]提出了關(guān)鍵鏈項(xiàng)目調(diào)度方法,該方法綜合考慮工序和資源約束來構(gòu)建項(xiàng)目調(diào)度計(jì)劃,并通過插入緩沖來提高項(xiàng)目調(diào)度的魯棒性,目前對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度的研究主要集中在識(shí)別關(guān)鍵鏈、計(jì)算緩沖方法等方面[3]。BIE等[4]提出了一種基于活動(dòng)依賴性的緩沖區(qū)大小確定方法。ZHANG等[5-6]在考慮工序和資源約束的基礎(chǔ)上,進(jìn)一步考慮了活動(dòng)之間的信息流,以最小化總協(xié)調(diào)成本為目標(biāo)來確定關(guān)鍵鏈排序,并研究了模糊資源約束下項(xiàng)目調(diào)度問題的緩沖計(jì)算方法。YANG等[7]提出了一種基于任務(wù)優(yōu)先級(jí)和關(guān)鍵鏈的多項(xiàng)目調(diào)度方法。
魯棒性資源分配的目的是找到魯棒性較好的資源傳遞路線來保護(hù)項(xiàng)目完工期。LEUS等[8]利用資源流網(wǎng)絡(luò)、分支定界算法對(duì)魯棒性資源分配問題進(jìn)行求解。DEBLAERE等[9]以最小化項(xiàng)目懲罰成本為目標(biāo),提出了3種基于整數(shù)規(guī)劃的資源分配的啟發(fā)式算法和一種最小化項(xiàng)目懲罰成本的構(gòu)建法MABO,并將這幾種算法與平行調(diào)度生成計(jì)劃和鏈?zhǔn)骄植空{(diào)度啟發(fā)式算法做了比較,結(jié)果顯示MABO算法得到的項(xiàng)目調(diào)度魯棒性最好。而近幾年關(guān)于資源分配算法的研究[10-11]主要關(guān)注于資源分配的算法效率,很少考慮資源分配算法的魯棒性效果。
傳統(tǒng)的關(guān)鍵鏈項(xiàng)目調(diào)度過程中并沒有預(yù)先確定資源在活動(dòng)間如何傳遞,資源一旦釋放便可用于其他任一未完成活動(dòng)。然而,實(shí)際項(xiàng)目的實(shí)施都會(huì)提前安排好資源(尤其是人力資源)的任務(wù)和流動(dòng)。在項(xiàng)目開始前安排好資源,有利于決策者做好外部活動(dòng)計(jì)劃,有利于員工提前知道自己未來的工作[12],所以在關(guān)鍵鏈項(xiàng)目調(diào)度中考慮資源分配很有必要。李俊亭[13]綜合分析了關(guān)鍵鏈項(xiàng)目進(jìn)度控制中的資源分配,提出了一種基于優(yōu)先規(guī)則的資源配置方案,但這種方案是響應(yīng)式的,沒有在制定項(xiàng)目調(diào)度計(jì)劃時(shí)考慮資源分配。
基于此,筆者將魯棒性資源分配應(yīng)用于關(guān)鍵鏈項(xiàng)目調(diào)度,提出了一種針對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度的主動(dòng)式資源分配方案來提高項(xiàng)目調(diào)度的魯棒性,以便使關(guān)鍵鏈調(diào)度計(jì)劃在執(zhí)行過程中能夠更好地抵御活動(dòng)工期的不確定性,提高完工率。同時(shí),通過大規(guī)模仿真實(shí)驗(yàn)進(jìn)一步分析了多種不同的資源分配對(duì)關(guān)鍵鏈調(diào)度計(jì)劃魯棒性的影響,驗(yàn)證了算法的有效性。
定義原始項(xiàng)目網(wǎng)絡(luò)為G=(N,A),N為節(jié)點(diǎn)集合,表示項(xiàng)目活動(dòng);A為箭線集合,代表活動(dòng)之間的先后關(guān)系。節(jié)點(diǎn)集合N={0,1,2,…,n},其中包括虛擬節(jié)點(diǎn)0和n。對(duì)于項(xiàng)目中的任意活動(dòng)j,其工期為dj,對(duì)第k(k=1,2,…,K)種資源的需求量為rjk,而每種資源的可利用量為ak,其中虛擬節(jié)點(diǎn)0和n的工期和資源消耗量均為0?;顒?dòng)的實(shí)際開始時(shí)間為Sj,計(jì)劃開始時(shí)間為sj。由分支定界算法得到的基準(zhǔn)計(jì)劃為S。
ARTIGUES等[14]最早提出資源流的概念,用來描述資源在活動(dòng)之間的流動(dòng)情況。資源流網(wǎng)絡(luò)G′=(N,AR)與原始項(xiàng)目網(wǎng)絡(luò)G=(N,A)的節(jié)點(diǎn)數(shù)相同,但是資源弧集合AR是連接節(jié)點(diǎn)i和節(jié)點(diǎn)j的箭線集合,且節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在任意一種資源k的資源流fijk(fijk>0)。假設(shè)每種資源k從虛擬開始活動(dòng)流出的資源總量等于流入虛擬結(jié)束活動(dòng)的總量,且等于該種資源的總可利用量ak,其數(shù)學(xué)表達(dá)式如式(1)所示。并且,一個(gè)可行的資源流網(wǎng)絡(luò)還必須滿足在每一個(gè)活動(dòng)節(jié)點(diǎn)的流量守恒,即對(duì)于每種資源k和每個(gè)非虛擬活動(dòng)i(i≠0,n),流入該活動(dòng)的總量必須等于流出量,且等于該活動(dòng)的資源需求量rik,其數(shù)學(xué)表達(dá)式如式(2)所示。
?k∈K
(1)
?i∈N{0,n},?k∈K
(2)
項(xiàng)目調(diào)度的魯棒性分為兩類:第一類是質(zhì)魯棒性, 指整個(gè)項(xiàng)目的完成時(shí)間的穩(wěn)定性,用按時(shí)完工率或完工期度量;第二類是解魯棒性, 指活動(dòng)開始時(shí)間的穩(wěn)定性[15]。在關(guān)鍵鏈項(xiàng)目調(diào)度中,多用不確定情況下的平均完工率(質(zhì)魯棒性)衡量調(diào)度計(jì)劃的魯棒性。對(duì)于同一個(gè)項(xiàng)目,滿足資源流網(wǎng)絡(luò)約束的資源分配方案可能有多種,筆者用一個(gè)小項(xiàng)目算例說明資源分配方案給項(xiàng)目魯棒性帶來的影響。
項(xiàng)目用AON網(wǎng)絡(luò)圖表示,如圖1所示,其中活動(dòng)1和活動(dòng)6分別為虛擬開始節(jié)點(diǎn)和虛擬結(jié)束節(jié)點(diǎn),圓圈內(nèi)數(shù)字代表活動(dòng)編號(hào),活動(dòng)上方數(shù)字為活動(dòng)時(shí)間,下方數(shù)字為活動(dòng)的資源需求,該項(xiàng)目只涉及一種可更新資源,資源總量為4個(gè)單位。
圖1 項(xiàng)目網(wǎng)絡(luò)圖
圖2 資源分配方案a
圖3 資源分配方案b
一種可行的資源分配方案a如圖2所示,可看出完工期為4個(gè)單位,活動(dòng)3的資源有一個(gè)來自活動(dòng)4,另一個(gè)來自活動(dòng)2。另一種資源分配方案b,如圖3所示,可看出活動(dòng)3所需的2個(gè)資源都來自活動(dòng)4,完工期同樣為4個(gè)單位。方案a中,活動(dòng)2或活動(dòng)4延遲1個(gè)單位時(shí)間都會(huì)造成活動(dòng)3不能按時(shí)開工,從而使得整個(gè)工期延長(zhǎng)。然而在其他條件相同的情況下,方案b中,只有活動(dòng)4延遲會(huì)影響活動(dòng)3,而活動(dòng)2延遲1個(gè)單位開始并不會(huì)影響整個(gè)工期,這種方案下的項(xiàng)目完工率會(huì)更加穩(wěn)定。可見,資源分配方案b的項(xiàng)目魯棒性比方案a更好。
至此電動(dòng)汽車最優(yōu)出行的約束條件便已完成,配合聯(lián)合目標(biāo)函數(shù),共同構(gòu)成了電動(dòng)汽車最優(yōu)出行路徑的規(guī)劃模型。由此模型,便能求解出任意初始位置與終止位置的最優(yōu)路徑。
項(xiàng)目調(diào)度中考慮資源分配本身是一種NP難題,筆者將針對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度,探索出一種具有較好魯棒性的資源分配方案。
關(guān)鍵鏈的長(zhǎng)度決定了項(xiàng)目工期,所以欲使項(xiàng)目盡快完工則需要保證關(guān)鍵鏈順利進(jìn)行。根據(jù)TOC思想,非關(guān)鍵鏈要盡可能“遷就”關(guān)鍵鏈,盡可能不讓非關(guān)鍵鏈活動(dòng)的延遲影響關(guān)鍵鏈活動(dòng),即減少非關(guān)鍵鏈活動(dòng)對(duì)關(guān)鍵鏈活動(dòng)的資源約束?;谝陨纤枷耄P者提出了關(guān)鍵鏈資源分配算法(critical chain resource allocation,CCRA),該算法以關(guān)鍵鏈活動(dòng)為核心,在不影響計(jì)劃最短完工期的情況下,優(yōu)先滿足關(guān)鍵鏈活動(dòng)的資源需求,盡量減少非關(guān)鍵鏈活動(dòng)對(duì)關(guān)鍵鏈活動(dòng)的資源約束,以保證關(guān)鍵鏈順利進(jìn)行,使得項(xiàng)目更加穩(wěn)健地執(zhí)行。算法按照活動(dòng)開始時(shí)間的先后順序,依次為其分配資源,提供資源的活動(dòng)為已完成的活動(dòng),且分配資源時(shí)滿足一定規(guī)則以得到魯棒性較好的資源分配方案。具體步驟如下:
(1)構(gòu)建基準(zhǔn)調(diào)度計(jì)劃并找出關(guān)鍵鏈。以最短工期為目標(biāo),使用DEMEULEMEESTER等[16]設(shè)計(jì)的分支定界算法生成項(xiàng)目基準(zhǔn)調(diào)度計(jì)劃S,通過活動(dòng)最早開始時(shí)間和最晚開始時(shí)間找到關(guān)鍵鏈。
(2)生成資源待分配的活動(dòng)順序Sequence。首先根據(jù)基準(zhǔn)調(diào)度計(jì)劃,按照活動(dòng)最早開始時(shí)間由小到大排列所有活動(dòng),開始時(shí)間相同的活動(dòng),先安排序號(hào)較小的活動(dòng)。然后在開始時(shí)間相同的活動(dòng)中將關(guān)鍵鏈活動(dòng)提前(為了優(yōu)先給關(guān)鍵鏈活動(dòng)分配資源),非關(guān)鍵鏈活動(dòng)順序不變,從而得到最終的資源待分配順序Sequence。
(3)初始化各活動(dòng)資源可供給數(shù)量,其值等于各活動(dòng)資源需求。
(4)依次為Sequence中的待分配活動(dòng)i找到可以為其提供資源的活動(dòng)序列Supply_set(在活動(dòng)i之前完成且資源供給不為零),該序列確定了為活動(dòng)i提供資源的活動(dòng)先后順序,其優(yōu)先規(guī)則如下:①如果活動(dòng)i是關(guān)鍵鏈活動(dòng),則優(yōu)先用其緊前的關(guān)鍵鏈活動(dòng)提供資源,再用緊前的非關(guān)鍵鏈活動(dòng)提供資源,最后用其他可提供資源的活動(dòng)(先完成的活動(dòng)優(yōu)先)提供資源;②如果活動(dòng)i是非關(guān)鍵鏈活動(dòng),則優(yōu)先用其緊前的非關(guān)鍵鏈活動(dòng)提供資源,再用緊前的關(guān)鍵鏈活動(dòng)提供資源,最后用其他可提供資源的活動(dòng)(先完成的活動(dòng)優(yōu)先)提供資源。
(5)分配資源。用提供資源的活動(dòng)集合Supply_set依次給當(dāng)前待分配資源的活動(dòng)i提供資源,更新活動(dòng)i的資源需求和提供資源活動(dòng)的供給數(shù)量,直到活動(dòng)i的資源需求被滿足。然后,轉(zhuǎn)步驟(4)分配下一個(gè)活動(dòng),直到所有活動(dòng)資源需求都被滿足。
步驟(4)中選擇先完成的活動(dòng)優(yōu)先提供資源是為了保證非關(guān)鍵鏈匯入關(guān)鍵鏈的總時(shí)差,因?yàn)闀r(shí)差越大,魯棒性越好。另外,如果活動(dòng)j要給活動(dòng)i分配資源,則應(yīng)盡可能多地分配資源(不超過活動(dòng)i的資源需求量),以減少額外資源約束。
為了更直觀地說明CCRA算法,筆者以圖1的簡(jiǎn)單項(xiàng)目為例演示具體資源分配步驟。
(1)得到最小完工期對(duì)應(yīng)的項(xiàng)目基準(zhǔn)調(diào)度計(jì)劃S=[0,0,2,0,2]。根據(jù)基準(zhǔn)調(diào)度計(jì)劃得到關(guān)鍵鏈為1→4→3→6。
(2)根據(jù)最早開始時(shí)間和關(guān)鍵鏈活動(dòng)得到資源待分配順序(不考慮虛擬活動(dòng))Sequence=[2,4,3,5],其中活動(dòng)2和活動(dòng)4開始時(shí)間相同,但活動(dòng)4是關(guān)鍵鏈活動(dòng),則活動(dòng)4在活動(dòng)2前被分配資源,得到最終活動(dòng)資源分配序列Sequence=[4,2,3,5]。
(3)初始化各活動(dòng)資源可供給數(shù)量,其值等于各活動(dòng)資源需求。
(4)分配資源。根據(jù)Sequence首先給活動(dòng)4分配資源:活動(dòng)4開始時(shí),可以提供資源的活動(dòng)為Supply_set4=[1],則f1,4=3(此時(shí),活動(dòng)4資源需求變?yōu)?,活動(dòng)1資源供給變?yōu)?);接著分配活動(dòng)2,Supply_set2=[1],則f1,2=1;分配活動(dòng)3,Supply_set3=[4,2](此時(shí)活動(dòng)4和活動(dòng)2都可提供資源,但因?yàn)榛顒?dòng)3是關(guān)鍵活動(dòng),優(yōu)先讓前序關(guān)鍵活動(dòng)4提供資源),則f4,3=2(此時(shí),活動(dòng)3資源需求變?yōu)?);分配活動(dòng)5,Supply_set5=[2,4](因?yàn)榛顒?dòng)5為非關(guān)鍵活動(dòng),優(yōu)先讓緊前非關(guān)鍵活動(dòng)2提供資源),則f2,5=1;活動(dòng)6為虛擬活動(dòng),需求為0,不作考慮。至此完成CCRA資源分配過程,得到資源分配結(jié)果即為圖3所示的魯棒性更好的分配方案。
對(duì)比兩種資源分配方案可以看出,相比于資源分配方案a,方案b做到了盡量“遷就”關(guān)鍵鏈,減少了2→3和4→5的兩個(gè)額外資源約束,且具體資源分配數(shù)量也有不同。
為了驗(yàn)證筆者所提資源分配算法的有效性,筆者使用Matlab軟件進(jìn)行大規(guī)模仿真實(shí)驗(yàn),選擇了PSPLIB實(shí)例集J30中具有代表性的48個(gè)項(xiàng)目例子進(jìn)行模擬仿真,比較不同的資源分配算法對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度計(jì)劃魯棒性的影響。對(duì)比的資源分配算法包括:隨機(jī)資源分配算法、MABO資源分配算法、筆者提出的關(guān)鍵鏈資源分配算法CCRA。隨機(jī)資源分配算法在進(jìn)行資源分配時(shí)不考慮任何魯棒性績(jī)效指標(biāo),實(shí)驗(yàn)中作為比較基準(zhǔn);MABO資源分配算法是目前資源受限型項(xiàng)目調(diào)度研究中能夠獲得較好魯棒性的一種資源分配算法。
實(shí)驗(yàn)中關(guān)鍵鏈項(xiàng)目調(diào)度計(jì)劃生成的具體步驟如下:①以最短工期為目標(biāo),構(gòu)建項(xiàng)目基準(zhǔn)調(diào)度計(jì)劃S,找出關(guān)鍵鏈活動(dòng)(使用文獻(xiàn)[16]提出的分支定界算法得到S,使用文獻(xiàn)[17]提出的方法查找關(guān)鍵鏈和非關(guān)鍵鏈)。②使用3種資源分配算法(隨機(jī)、MABO、CCRA)得到具體資源分配方案。③根據(jù)工序約束和資源約束,分別重新確定非關(guān)鍵鏈(關(guān)鍵鏈不變)。④在非關(guān)鍵鏈與關(guān)鍵鏈匯合處插入?yún)R入緩沖FB(使用剪切粘貼法,大小為50%的非關(guān)鍵鏈長(zhǎng)度[18]),筆者不考慮項(xiàng)目緩沖。⑤調(diào)整緩沖大小解決二次資源沖突(斷開關(guān)鍵鏈),輸出關(guān)鍵鏈調(diào)度計(jì)劃。⑥將生成的1 000次模擬活動(dòng)時(shí)間按照3種不同的調(diào)度計(jì)劃執(zhí)行,分別統(tǒng)計(jì)魯棒性指標(biāo)。
式中:wi為每個(gè)活動(dòng)權(quán)重,表示該活動(dòng)延遲一個(gè)時(shí)間單位開工所造成的損失;Si和Si*分別表示活動(dòng)i的計(jì)劃開始時(shí)間和仿真執(zhí)行中的實(shí)際開始時(shí)間。
3種資源分配算法的仿真結(jié)果如表1所示,MABO和CCRA兩種算法相對(duì)隨機(jī)資源分配的優(yōu)化百分比統(tǒng)計(jì)如表2所示。由表1可知,隨著活動(dòng)工期不確定性(σ)的增加,3種方法各自的平均懲罰成本都增加,平均按時(shí)完工率降低,平均完工時(shí)間增加。符合項(xiàng)目的不確定越大,越會(huì)影響項(xiàng)目的執(zhí)行的規(guī)律。結(jié)合表1和表2結(jié)果對(duì)比分析3種資源分配算法,在σ=0.3的水平下,平均按時(shí)完工率最高的是CCRA算法,為92.58%,優(yōu)化百分比為2.66%;在σ=0.6的水平下,CCRA算法的平均按時(shí)完工率最高,為59.55%,提高比率為9.67%;在σ=0.9的水平下,完工率依然是CCRA算法表現(xiàn)最好。隨著活動(dòng)時(shí)間不確定性的增加,在按時(shí)完工率和平均完工時(shí)間方面,CCRA算法的效果一直保持最好,具有一致性。所以,就質(zhì)魯棒性而言,CCRA算法比另外兩種算法更優(yōu)。
表1 3種資源分配算法仿真結(jié)果
在解魯棒性方面,當(dāng)σ=0.3時(shí),MABO算法的平均懲罰成本低于CCRA算法,而當(dāng)σ=0.6和σ=0.9時(shí),CCRA算法的平均懲罰成本低于MABO算法??梢?,雖然MABO算法的目標(biāo)函數(shù)是最小化懲罰成本,但是在“接力賽”執(zhí)行策略中,效果并非一直最好。所以,就解魯棒性而言,隨著活動(dòng)時(shí)間不確定性的增加,CCRA算法的表現(xiàn)也會(huì)比MABO算法好。出現(xiàn)這種結(jié)果的一種可能的解釋是,當(dāng)活動(dòng)不確定性較小時(shí),活動(dòng)工期波動(dòng)不大,因而緩沖消耗不大,在接力賽的執(zhí)行策略下,CCRA算法的完工率高,活動(dòng)基本提前完工,導(dǎo)致活動(dòng)的實(shí)際開始時(shí)間與計(jì)劃時(shí)間偏差較大;而隨著活動(dòng)時(shí)間不確定性的增大,CCRA算法在懲罰成本方面的優(yōu)勢(shì)就能體現(xiàn)出來,MABO算法因?yàn)橛?jì)劃完工期延期較多,完工率低,以致懲罰成本這一指標(biāo)也不如CCRA算法。
表2 算法優(yōu)化百分比 %
此外,實(shí)驗(yàn)還統(tǒng)計(jì)了3種算法的平均耗時(shí),即48個(gè)項(xiàng)目生成關(guān)鍵鏈調(diào)度計(jì)劃并執(zhí)行該計(jì)劃所耗平均時(shí)間(其他參數(shù)完全相同):隨機(jī)資源分配算法的平均耗時(shí)為14.311 s,CCRA算法的平均耗時(shí)為14.765 s,而MABO算法的平均耗時(shí)為314.611 s??梢?,CCRA算法的效率較MABO算法有顯著提高。因此,在制定項(xiàng)目調(diào)度計(jì)劃時(shí),運(yùn)用不同的資源分配方案確實(shí)會(huì)影響項(xiàng)目執(zhí)行的魯棒性,并且,優(yōu)先保證關(guān)鍵鏈上活動(dòng)執(zhí)行的資源分配方案能夠有效提高項(xiàng)目的魯棒性。
將項(xiàng)目管理領(lǐng)域中相對(duì)獨(dú)立的魯棒性資源分配研究和關(guān)鍵鏈項(xiàng)目管理研究相結(jié)合,提出了新的能有效提高關(guān)鍵鏈項(xiàng)目調(diào)度計(jì)劃魯棒性的資源分配方法。在傳統(tǒng)關(guān)鍵鏈項(xiàng)目調(diào)度過程中考慮魯棒性資源分配,通過一個(gè)算例說明了資源分配方案的不同會(huì)對(duì)項(xiàng)目調(diào)度魯棒性產(chǎn)生影響,進(jìn)而針對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度的特點(diǎn),提出了關(guān)鍵鏈資源分配算法CCRA。CCRA算法的主要思想是優(yōu)先滿足關(guān)鍵鏈活動(dòng)的資源需求,并盡量減少非關(guān)鍵鏈活動(dòng)資源向關(guān)鍵鏈活動(dòng)傳遞的路徑,從而減少非關(guān)鍵活動(dòng)對(duì)關(guān)鍵鏈活動(dòng)的影響,保護(hù)項(xiàng)目完工期。
通過大規(guī)模仿真實(shí)驗(yàn)對(duì)比了3種不同的資源分配方法對(duì)關(guān)鍵鏈項(xiàng)目調(diào)度魯棒性的影響,驗(yàn)證了CCRA算法的有效性。實(shí)驗(yàn)結(jié)果表明:活動(dòng)執(zhí)行時(shí)間不確定性(σ)越高,則項(xiàng)目完工率越低,懲罰成本越高;在同一活動(dòng)時(shí)間不確定性水平下,CCRA算法得到的項(xiàng)目調(diào)度計(jì)劃質(zhì)魯棒性(完工率、完工期)最好,解魯棒性(懲罰成本)總體也優(yōu)于其他兩種算法;相比于目前效果較好的MABO資源分配算法,CCRA算法的計(jì)算效率更高。可見,不同的資源分配方案會(huì)影響關(guān)鍵鏈項(xiàng)目調(diào)度的魯棒性,CCRA算法可以得到魯棒性更好的關(guān)鍵鏈項(xiàng)目調(diào)度計(jì)劃,更加適用于關(guān)鍵鏈項(xiàng)目調(diào)度。
未來有關(guān)關(guān)鍵鏈項(xiàng)目調(diào)度的研究,可進(jìn)一步探究魯棒性資源分配對(duì)緩沖控制會(huì)產(chǎn)生何種影響,以便為項(xiàng)目的緩沖控制提供更多的管理方法和啟示。
武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)2018年5期