張靜文， 劉耕濤

(西北工業(yè)大學(xué) 管理學(xué)院，陜西 西安 710072)

?

魯棒性視角下的關(guān)鍵鏈項目調(diào)度新方法

張靜文， 劉耕濤

(西北工業(yè)大學(xué) 管理學(xué)院，陜西 西安 710072)

探究傳統(tǒng)關(guān)鍵鏈方法在實踐應(yīng)用中出現(xiàn)的問題并提出改進措施。首先剖析出三個方面的不足：第一，基準(zhǔn)調(diào)度計劃不唯一；第二，非關(guān)鍵鏈的識別方式導(dǎo)致輸入緩沖失效；第三，對插入輸入緩沖時引起的二次資源沖突問題，現(xiàn)有的解決方法與緩沖的本質(zhì)作用相背離。據(jù)此，基于魯棒性調(diào)度優(yōu)化的思想，采用理論分析和案例說明相結(jié)合，針對三個方面分別提出了相應(yīng)的解決方案，形成魯棒性視角下的關(guān)鍵鏈項目調(diào)度新方法。研究結(jié)論對于將關(guān)鍵鏈方法科學(xué)地應(yīng)用于項目管理實踐提供了理論指導(dǎo)。

關(guān)鍵鏈；調(diào)度計劃；輸入緩沖；資源沖突；二次調(diào)度

0 引言

Goldratt提出的關(guān)鍵鏈方法(Critical Chain Method/Critical Chain, CCM/CC)[1]被認(rèn)為是繼經(jīng)典CPM/PERT(Critical Path Method/Program Evaluation and Review Technology)之后項目管理技術(shù)發(fā)展中的又一重大里程碑事件?，F(xiàn)代項目結(jié)構(gòu)及規(guī)模日趨復(fù)雜，面臨環(huán)境日益多變，項目外部的不確定性和風(fēng)險不斷增大；同時，經(jīng)濟全球化導(dǎo)致市場競爭日趨激烈，眾多項目對稀缺資源的競爭愈加激烈，經(jīng)典CPM/PERT已不能適應(yīng)項目管理實踐的需要，而CCM在應(yīng)對不確定的項目實施環(huán)境時具有一定的效果[2]。CCM從人的行為特征、資源約束和活動工期三個方面突破了經(jīng)典的項目管理方法，是一種管理理念上的提升[3]。然而，任何一種理論或方法都需要根據(jù)適用環(huán)境的改變而不斷改進，針對目前CCM在應(yīng)用中存在的三個突出問題，本文從魯棒性(Robustness)調(diào)度優(yōu)化角度，提出一種魯棒性視角下關(guān)鍵鏈項目調(diào)度新方法。為表述方便，本文中將Goldratt提出的關(guān)鍵鏈方法稱為傳統(tǒng)CCM。

1 魯棒性和關(guān)鍵鏈中的魯棒性內(nèi)涵分析

魯棒性項目調(diào)度作為一種不確定型項目調(diào)度理論，是目前項目調(diào)度領(lǐng)域的研究熱點之一[4，5]。魯棒性調(diào)度指調(diào)度計劃的穩(wěn)健性，即能夠抵控由于不可控因素導(dǎo)致的計劃拖延，使項目的完成過程具有較好的穩(wěn)定性。Al-Fawzan等人[6]首先將魯棒性概念真正引入資源約束項目調(diào)度問題(Resource-constrained Project Scheduling Problem, RCPSP)，采用資源約束下活動的自由時差之和來度量調(diào)度方案的魯棒性。Vonder等人[7]將調(diào)度魯棒性區(qū)分為兩類：第一類是質(zhì)量魯棒性(quality robustness)，指調(diào)度計劃對于績效目標(biāo)的穩(wěn)定性，如對項目工期的穩(wěn)定性；第二類是解的魯棒性(solution robustness)，指調(diào)度過程的細節(jié)，如活動開始時間的穩(wěn)定性。Chtourou等人[8]針對活動工期拖延的RCPSP，提出一種基于優(yōu)先規(guī)則的兩階段算法，借助12種指標(biāo)最大化調(diào)度計劃的魯棒性。劉瓊[9]等人以魯棒性和多項目工期為目標(biāo)研究多項目魯棒性調(diào)度模型，然而他們并沒有關(guān)注到傳統(tǒng)CCM在應(yīng)用過程中的一些最基本的問題。

關(guān)鍵鏈?zhǔn)窃跐M足資源約束和活動間相互依賴的關(guān)系下，制約項目工期的最長的活動鏈。根據(jù)活動的估計工期和資源限量識別出項目網(wǎng)絡(luò)的關(guān)鍵鏈和非關(guān)鍵鏈。在非關(guān)鍵鏈匯入關(guān)鍵鏈入口處設(shè)置FB，用來吸收由于非關(guān)鍵活動的拖延對關(guān)鍵鏈的影響；在關(guān)鍵鏈末端設(shè)置PB，用來吸收由于關(guān)鍵鏈上的活動拖延對項目工期的影響。CCM中蘊含的魯棒性思想分析如下：

(1)緩沖機制層面的魯棒性：CCM通過在調(diào)度計劃中設(shè)置緩沖機制來消除不確定因素對實施調(diào)度計劃的影響，緩沖的本質(zhì)作用是吸收活動工期的拖延并將其在項目執(zhí)行過程中進行消化。CCM的精髓在于緩沖機制，而緩沖使得項目計劃具有一定的抗外界變化環(huán)境干擾的魯棒性特征。

(2)緩沖微觀層面的魯棒性：在CCM計劃中，各FB的大小通常由對應(yīng)的非關(guān)鍵鏈上活動的安全時間確定，唯一的PB的大小由關(guān)鍵鏈上的活動的安全時間來確定。因此，從時差角度分析，設(shè)置FB本質(zhì)是對某條非關(guān)鍵鏈上所有活動時差的集中管理，設(shè)置PB本質(zhì)是對關(guān)鍵鏈上所有活動時差的集中管理；各FB分散在調(diào)度計劃的各個階段，期望保證調(diào)度計劃在執(zhí)行過程中的穩(wěn)定性，體現(xiàn)了解的魯棒性；PB置于調(diào)度計劃末端，期望保證項目工期的穩(wěn)定性，體現(xiàn)了質(zhì)量魯棒性。因此，從兩類緩沖的位置和大小的微觀層面看，F(xiàn)B和PB分別體現(xiàn)了解的魯棒性和質(zhì)量魯棒性。

盡管CCM中蘊含了魯棒優(yōu)化調(diào)度的思想，然而傳統(tǒng) CCM中僅考慮項目工期目標(biāo)，忽略了能體現(xiàn)關(guān)鍵鏈重要特質(zhì)的魯棒性指標(biāo)，所以傳統(tǒng)的關(guān)鍵鏈概念是狹義上的，這也直接制約了傳統(tǒng)CCM更廣泛地應(yīng)用于實踐。本文首先剖析了傳統(tǒng)CCM在實踐應(yīng)用中的三個方面的不足，據(jù)此針對每個方面分別提出了基于魯棒優(yōu)化調(diào)度思想的改進策略，形成了魯棒性視角下的關(guān)鍵鏈項目調(diào)度新方法的主要內(nèi)容。

2 傳統(tǒng)CCM的不足

圖1 包含10個實活動的項目網(wǎng)絡(luò)及參數(shù)

2.1 存在多個基準(zhǔn)調(diào)度方案

在某一資源限量下，最短項目工期可能對應(yīng)多個不同的基準(zhǔn)調(diào)度方案S，每個S都可以確定活動網(wǎng)絡(luò)的關(guān)鍵鏈和非關(guān)鍵，但是究竟選擇哪一個基準(zhǔn)調(diào)度計劃作為插入FB后執(zhí)行二次調(diào)度計劃的依據(jù)，傳統(tǒng)CCM沒有涉及此問題。例如對圖1中的活動網(wǎng)絡(luò)，當(dāng)資源限量R=7時，采用分支定界算法獲得的最短項目工期為26，對應(yīng)兩種不同的基準(zhǔn)調(diào)度計劃如圖2所示。

圖2a 基準(zhǔn)調(diào)度計劃S1

圖2b 基準(zhǔn)調(diào)度計劃S2

在圖2中，虛線鏈接起來的活動構(gòu)成CC。在圖2a中，CC為4→5→6→8→10，在圖2b中，CC為2→4→7→5→6→8→10。在這種情形下，選擇哪一個作為實施CCM的基準(zhǔn)調(diào)度計劃來確定輸入緩沖的位置和尺寸，需要進一步?jīng)Q策。請注意，這點與傳統(tǒng)CCM中提到的存在多條CC的情形不同，后者提及的多條CC指基于同一個S，基于網(wǎng)絡(luò)結(jié)構(gòu)中的鏈路結(jié)構(gòu)關(guān)系而形成的多條CC。

2.2 輸入緩沖的設(shè)置方式

2.3 輸入緩沖引起的資源沖突問題

3 改進的CCM

針對傳統(tǒng)CCM中存在的上述三個方面的問題，我們分別提出了解決方法，形成了基于魯棒性視角下的新的CCM。

3.1 確定唯一的基準(zhǔn)調(diào)度計劃

當(dāng)最短項目工期對應(yīng)多個S時，如何確定某個S作為實施CCM的基準(zhǔn)調(diào)度計劃。我們提出兩種解決方案：

(1)客觀的方式

很清楚，不同的調(diào)度計劃中具有不同的關(guān)鍵活動集合和非關(guān)鍵活動集合，因此不同S中具有不同的時差分布和不同的輸入緩沖設(shè)置狀態(tài)(位置及尺寸)。CCM的基本思想是通過插入緩沖來確保調(diào)度計劃在實施中的穩(wěn)定性?；诖?，我們提出從魯棒性目標(biāo)的角度進一步區(qū)分多個調(diào)度方案的優(yōu)劣。借鑒基本RCPSP中的魯棒性度量方式來量化每個S的魯棒性指標(biāo)，比如最直觀地，以調(diào)度計劃中所有非關(guān)鍵活動的自由時差和來體現(xiàn)魯棒性。對于圖2中的兩種調(diào)度方案S1和S2，從魯棒性調(diào)度優(yōu)化角度分析，自由時差在S1中的分布比在S2中更分散，即S1中具有更多的非關(guān)鍵活動，因此S1對活動拖延的吸收能力比S2強。采用Lambrechts等人[13]提出的基于時差效用函數(shù)的魯棒性度量公式來量化兩種調(diào)度方案的魯棒性：

(2)主觀的方式

盡管最短項目工期可能對應(yīng)多個基準(zhǔn)調(diào)度方案，但是通常此基準(zhǔn)調(diào)度方案的總數(shù)較少。此時項目經(jīng)理可以根據(jù)其實踐經(jīng)驗來選擇其中一個作為實施CCM的基準(zhǔn)調(diào)度方案。比如，如果在某個基準(zhǔn)調(diào)度方案的CC中，包含了較多對項目實施過程產(chǎn)生重大影響的活動，則此時就可以選此方案作為基準(zhǔn)調(diào)度方案。例如對圖2中的S1和S2，兩種方案的差別在于是否選擇活動2和活動7作為關(guān)鍵活動，如果根據(jù)項目經(jīng)理的判斷，這兩個活動的工作內(nèi)容對整個項目的實施起著關(guān)鍵性的作用，則此時就選擇S2作為基準(zhǔn)調(diào)度方案，否則，將選擇S1。進一步，基于選定的基準(zhǔn)調(diào)度方案確定FB(位置和尺寸)和PB的尺寸。

3.2 輸入緩沖的合理設(shè)置

圖3 基于圖2a設(shè)置各FB

改進的設(shè)置FB的方法使得各條FB起到了應(yīng)有的作用，同時盡可能地保證關(guān)鍵活動的如期執(zhí)行，最終將使實際進度更接近于制定的調(diào)度計劃，同時也能夠體現(xiàn)出CCM是一種前攝性的魯棒調(diào)度優(yōu)化方法。

3.3 消除資源沖突的魯棒性策略

針對2.3中的問題設(shè)計解決方法，傳統(tǒng)CCM并沒有充分考慮所獲得的二次調(diào)度計劃在實施中的效果。通常項目經(jīng)理希望實際進度與調(diào)度計劃的偏離盡可能地小，以此來減小由于計劃變更導(dǎo)致的轉(zhuǎn)換費用并節(jié)省時間。同時，項目經(jīng)理也需要制定出的調(diào)度計劃具有一定的柔性，即當(dāng)實際活動工期偏離計劃工期時，對進度計劃作最小的調(diào)整即可以重新獲得較優(yōu)的調(diào)度計劃。因此，從實施項目計劃的動態(tài)角度出發(fā)，項目經(jīng)理期望CCM給出的調(diào)度計劃能夠具有較好的魯棒性。所以，基于魯棒調(diào)度優(yōu)化的思想，針對插入FB導(dǎo)致的資源沖突問題，本文提出一種啟發(fā)式的協(xié)調(diào)策略，即在二次調(diào)度計劃中的活動偏好規(guī)則。首要地，二次調(diào)度計劃基于基準(zhǔn)調(diào)度計劃進行，具體說明如下：

(1)從起始時間開始，根據(jù)時間點從前向后依次插入每個FB；當(dāng)發(fā)生資源沖突時，僅解決當(dāng)前緩沖插入位置到下一個輸入緩沖插入點之間的資源沖突。

(2)當(dāng)插入FB時導(dǎo)致發(fā)生資源沖突的活動同時涉及關(guān)鍵活動和非關(guān)鍵活動時，首先保證關(guān)鍵活動的開始時間不變，向右移動非關(guān)鍵活動，同時與此非關(guān)鍵活動相聯(lián)系的FB中應(yīng)減去后移的時間量。

(3)當(dāng)插入FB后導(dǎo)致發(fā)生資源沖突的活動僅涉及關(guān)鍵活動時，此時必須后移關(guān)鍵活動的開始時間。并且，當(dāng)后移某個關(guān)鍵活動時，將從PB中減去關(guān)鍵活動后移的時間量。PB被消蝕完之后，繼續(xù)有關(guān)鍵活動后移表示項目工期增加。

(1)實際項目進展中，非關(guān)鍵鏈上活動的拖延未超過其鏈路具有的自由時差時，即緩沖的實際消耗并未引起資源沖突。盡管二次調(diào)度計劃后移了緊隨其后的關(guān)鍵活動的開始時間，但是此時可以不根據(jù)二次調(diào)度計劃的時間開始關(guān)鍵活動，而根據(jù)其最早開始時間開始緊后的關(guān)鍵活動，這相當(dāng)于在二次計劃中刪掉了多余的緩沖時間，其之后的活動調(diào)度計劃整體前移，而不必對計劃進行重新調(diào)度。

(2)起到了將PB分散到調(diào)度計劃過程中的效果。在項目實施中，當(dāng)某個關(guān)鍵活動拖延時，其拖延通過鏈條的傳遞作用將影響之后的每個關(guān)鍵活動，如果仍保持之后的非關(guān)鍵活動的開始時間不變，則很可能引起后面調(diào)度計劃中多處出現(xiàn)資源沖突。然而，通過上面消除沖突的策略，在二次調(diào)度中將某些關(guān)鍵活動后移的同時也相當(dāng)于給被后移的關(guān)鍵活動的緊前關(guān)鍵活動設(shè)置了緩沖，當(dāng)前面的緊前活動有拖延時，此處設(shè)置的FB可以吸收這種拖延，而由于后推關(guān)鍵活動導(dǎo)致的資源沖突問題在實施二次調(diào)度計劃過程中已經(jīng)考慮到了，最終達到項目實際進展中對調(diào)度計劃偏離盡可能小的目的。因此，如此設(shè)置FB和消除資源沖突的策略，相當(dāng)于將PB分散到了調(diào)度計劃中的一些關(guān)鍵活動之后。

基于上述三個方面的研究：(a)根據(jù)魯棒性目標(biāo)確定唯一的基準(zhǔn)調(diào)度計劃；(b)結(jié)合基準(zhǔn)調(diào)度計劃和網(wǎng)絡(luò)結(jié)構(gòu)關(guān)系識別非關(guān)鍵和設(shè)置FB；(c)消除FB引起的資源沖突的啟發(fā)式二次魯棒性調(diào)度策略，本文形成了魯棒性視角下的新的CCM。

4 結(jié)束

傳統(tǒng)CCM的管理理念得到了認(rèn)可，然而它在項目管理實踐中的應(yīng)用卻面臨一些困惑。本文針對傳統(tǒng)CCM在應(yīng)用過程中的三個不足提出解決方案。首先，對于最短項目工期對應(yīng)的基準(zhǔn)調(diào)度不唯一的情形，提出了進一步從魯棒性目標(biāo)角度或根據(jù)項目經(jīng)理的知識經(jīng)驗來確定唯一的基準(zhǔn)調(diào)度方案。其次，針對設(shè)置FB時忽略了基準(zhǔn)調(diào)度計劃而導(dǎo)致FB失效，提出了將基準(zhǔn)調(diào)度計劃和網(wǎng)絡(luò)結(jié)構(gòu)鏈路關(guān)系結(jié)合起來設(shè)置FB的方法。第三，插入FB可能引起二次調(diào)度中的資源沖突問題，分析了現(xiàn)有方法的缺陷，提出了基于魯棒調(diào)度優(yōu)化思想的解決緩沖資源沖突的策略。研究工作期望對CCM在項目管理實踐中的應(yīng)用提供指導(dǎo)。

由于偏幅所限，本文僅通過一個實例說明了魯棒性視角下的關(guān)鍵鏈項目調(diào)度新方法的有效性，緊隨的研究工作將從優(yōu)化模型的構(gòu)建、魯棒性指標(biāo)的設(shè)計及有效性測度、開發(fā)模型的求解算法和大規(guī)模算例的仿真測試等方面，比較新方法和傳統(tǒng)CCM的效果，以進一步從理論上證明新方法對實踐的有效性。另一方面，CCM在本質(zhì)上是一種前攝性的魯棒項目調(diào)度優(yōu)化方法，而目前對CCM的定義僅局限于工期最短的框架下，魯棒性目標(biāo)并沒有在CCM方法中體現(xiàn)出來，且工期最短的調(diào)度方案并不一定魯棒性也最好。因此，同時考慮工期和魯棒性目標(biāo)的多目標(biāo)CCM將是我們下一步的研究內(nèi)容。

[1] Goldratt E M. Critical Chain[M]. Great Barrington: The North River Press Publishing Corporation, 1997.

[2] Herroelen W, Lues R. Project scheduling under uncertainty: survey and research potentials[J]. European Journal of Operational Research, 2005, 165(2): 289-306.

[3] 張靜文,李若楠.關(guān)鍵鏈項目調(diào)度方法研究評述[J].控制與決策,2013,28(9):1281-1287.

[4] Deblaere F, Demeulemeester E, Herroelen W. Reactive scheduling in the multi-mode RCPSP[J]. Computer & Operations Research, 2011, 38(1): 63-74.

[5] 龐南生,孟俊姣.多目標(biāo)資源受限項目魯棒調(diào)度研究[J].運籌與管理,2012,21(3):27-32.

[6] Al-fawzan M A, Haouari M. A bi-objective model for robust resource-constrained project scheduling[J]. International Journal of Production Economics, 2005, 96(2): 175-187.

[7] Vonder S V, Demeulemeester E, Herroelen W, Leus R. The use of buffers in project management: the trade-off between stability and makespan[J]. International Journal of Production Economics, 2005, 97(2): 227-240.

[8] Chtourou H, Haouari M. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling[J]. Computer & Industrial Engineering, 2008, 55(1): 183-194.

[9] 劉瓊,林魁,張超勇,朱海平.基于關(guān)鍵鏈多項目魯棒調(diào)度[J].計算機集成制造系統(tǒng),2012,18(4):813- 820.

[10] 劉士新,宋健海,唐加福.資源受限項目調(diào)度中緩沖區(qū)的設(shè)定方法[J].系統(tǒng)工程學(xué)報,2006,21(4):381-386.

[11] 彭武良,金敏力,紀(jì)國燾.多模式關(guān)鍵鏈項目調(diào)度及啟發(fā)式求解[J].計算機集成制造系統(tǒng),2012,25(1):123-131.

[12] 田文迪,崔南方,付樟華.基于分支定界法的關(guān)鍵鏈項目計劃重排[J].計算機應(yīng)用研究,2011,28(11):4035- 4039

[13] Lambrechts O, Demeulemeester E, Herroelen W. A tabu search procedure for developing robust predictive project schedules[J]. International Journal of Production Economics, 2008, 111(2): 493-508.

An Improved Critical Chain Project Scheduling Method in thePerspective of Robustness

ZHANG Jing-wen, LIU Geng-tao

(School of Management, Northwestern Polytechnical University, Xi′an 710072, China)

We investigate some puzzles in practice from the traditional critical chain method (CCM), and several correcting measures are put forward. Three pitfalls of the CCM are pointed out in this paper. Firstly, the baseline schedules are not unique. Secondly, the effect of feeding buffers fails because of the improper means to identify non-critical chains. Thirdly, the existing ways, which are used to eliminate the second resource conflicts resulting from the insertion of feeding buffers, deviate from the nature role of feeding buffers. Accordingly, based on the thought of robust optimization, three solutions are respectively presented to overcome the three drawbacks by integrating theoretical analyses and case interpretations. Therefore, a new critical chain project scheduling method is formed based on the three aspects of improvements on the traditional CCM. The results show that our new CCM can provide the scientific instructions for project managers when they adopt the CCM in reality.

critical chain; schedule; feeding buffer; resource confliction; rescheduling

2013- 07-17

國家自然科學(xué)基金資助項目(70702026)；陜西省自然科學(xué)基金資助項目(2011JQ9001,2015JM7368)；西北工業(yè)大學(xué)管理振興及管理學(xué)院優(yōu)秀青年教師培養(yǎng)資助計劃(RW201309)；校研究生創(chuàng)業(yè)種子基金資助項目(Z2014075)

張靜文(1976-)，女，陜西人，副教授，研究方向為項目調(diào)度優(yōu)化的理論和方法。

C935，F(xiàn)224.3

A

1007-3221(2015)03- 0197- 08