基于活動重心定理的關(guān)鍵鏈識別法

王　藝， 崔南方

(1.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430074；2.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

?

基于活動重心定理的關(guān)鍵鏈識別法

王藝1,2， 崔南方1

(1.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430074；2.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063)

針對關(guān)鍵鏈識別這一關(guān)鍵鏈調(diào)度理論的基本問題，建立了以活動重心為優(yōu)先規(guī)則的兩階段關(guān)鍵鏈識別啟發(fā)式求解方法。并運(yùn)用數(shù)理統(tǒng)計學(xué)假設(shè)檢驗(yàn)方法，以Patterson110問題集為樣本，將新構(gòu)建的算法與三種基于較好優(yōu)先規(guī)則的啟發(fā)式算法進(jìn)行了比較，統(tǒng)計數(shù)據(jù)說明論文構(gòu)建的迭代重心法有一定的先進(jìn)性，同時極大地簡化了關(guān)鍵鏈的識別過程。

關(guān)鍵鏈識別； 活動重心； 優(yōu)先規(guī)則

關(guān)鍵鏈項(xiàng)目管理(critical chain project management，CCPM)是Goldratt于1997年提出的項(xiàng)目管理領(lǐng)域的新理論。找出制約項(xiàng)目順利完成的瓶頸-關(guān)鍵鏈，并在行為假設(shè)的前提下，運(yùn)用緩沖技術(shù)來保護(hù)關(guān)鍵鏈，從而實(shí)現(xiàn)在動態(tài)環(huán)境中保護(hù)項(xiàng)目整體的思想，是關(guān)鍵鏈項(xiàng)目管理方法顯著區(qū)別于現(xiàn)有項(xiàng)目管理技術(shù)，并受到持續(xù)推崇的根本原因。

CCPM關(guān)注和解決的基本問題是經(jīng)典的、面向時間優(yōu)化的資源受限項(xiàng)目計劃與調(diào)度問題(resource constrained project scheduling problem，RCPSP)[1-2]。與之不同的是，CCPM較傳統(tǒng)的RCPSP問題的求解又前進(jìn)了一步，它并不停止于得到問題最優(yōu)或者近優(yōu)解，還需進(jìn)一步識別制約項(xiàng)目進(jìn)度的關(guān)鍵鏈，并以此為基礎(chǔ)進(jìn)行計劃的調(diào)度。

Leach[3]、Tukel等[4]、莫巨華[5]、田文迪和崔南方[6]、Rabbani[7]、管在林等[8]、馬國豐等[9]分別從不同角度構(gòu)建了啟發(fā)式的關(guān)鍵鏈識別算法，但都以RCPSP問題的求解為基礎(chǔ)。眾所周知，RCPSP問題屬于NP Hard問題，主要有精確算法和啟發(fā)式求解法。啟發(fā)式計算方法又分為基于優(yōu)先規(guī)則的啟發(fā)式求解法和元啟發(fā)式求解法(又稱智能優(yōu)化算法[10])。然而從可接受的計算時間和計算效率考慮，基于優(yōu)先規(guī)則的啟發(fā)式求解算法仍然是實(shí)際生產(chǎn)運(yùn)作以及商業(yè)軟件中使用最廣泛的技術(shù)方法。但是不同啟發(fā)式規(guī)則的使用會對同一項(xiàng)目調(diào)度問題產(chǎn)生不同的結(jié)果，進(jìn)而影響到關(guān)鍵鏈的識別以及關(guān)鍵鏈項(xiàng)目管理方法的使用效果。因此探索先進(jìn)的基于優(yōu)先規(guī)則的關(guān)鍵鏈識別算法具有理論和實(shí)際雙重意義。

本文擬構(gòu)建一個兩階段關(guān)鍵鏈識別的啟發(fā)式求解算法。第一階段針對單項(xiàng)目、經(jīng)典RCPSP問題的求解，介紹一種新的優(yōu)先規(guī)則—活動的重心(the activity’s center of gravity，ACG)，以最小活動重心為活動進(jìn)行優(yōu)先值賦權(quán)，采用并行調(diào)度法則[11]，聯(lián)合正、反向迭代技術(shù)[12-15]，建立一種新的面向RCPSP問題的啟發(fā)式求解方法；第二階段進(jìn)行關(guān)鍵鏈的識別，根據(jù)第一階段迭代計算得到的不同結(jié)果，進(jìn)一步利用活動的執(zhí)行時間參數(shù)或者動態(tài)規(guī)劃的方法進(jìn)行關(guān)鍵鏈的識別。

1　活動的重心及重心定理

1.1活動的重心(ACG)及虧值定理

1.1.1活動的重心

活動的重心一值是乞建勛在文獻(xiàn)[16]中提出的，計算公式為

ACGi=ESi+LFi=ESi+(ESi+Di+TFi)=2ESi+TFi+Di,

(1)

ESi，LFi分別為CPM網(wǎng)絡(luò)下活動i的最早開始時間和最遲完成時間；Di為活動i的工期；TFi為活動i的總時差。同時該論著探討了CPM網(wǎng)絡(luò)下n元序鏈的優(yōu)化問題，提出了一般n元序鏈虧值定理。

1.1.2n元序鏈虧值定理

當(dāng)n個平行工序A1，A2，…，An調(diào)整為順序工序，即A1→A2→…→An時，稱后者為n元序鏈；由工序順序化所產(chǎn)生的項(xiàng)目工期延遲稱為n元序鏈的虧值，記為[A1A2…An]。

[A1A2…An]=max{T1,T2,…,Tn-1,0},

(2)

Tk為n元序鏈第k階(1≤k≤n)特征值：

Tk= EFA1 A2 …AK-LSAk+1，

(3)

LS 為CPM網(wǎng)絡(luò)下活動的最晚開始時間。

1.1.3重心定理

利用n元序鏈虧值定理，可以證明重心定理：當(dāng)2個平行工序順序化時，將重心較小的工序排列在前，獲得的次序最優(yōu)，帶來的項(xiàng)目工期延遲最小，當(dāng)項(xiàng)目網(wǎng)絡(luò)中其它條件不變時。

當(dāng)3個平行工序順序化時，情形開始變得復(fù)雜，需要一些附加條件才能夠判斷最優(yōu)次序。對于此問題，乞建勛證明了首工序定理和末工序定理。

[首工序定理] 若ESA≤ESB，ESC,且LFA≤LFB,LFC，則A一定在最優(yōu)鏈的首位。即最優(yōu)鏈?zhǔn)?A→B→C)或者(A→C→B)。

[末工序定理] 若ESA，ESB≤ESC,且LFA，LFB≤LFC，則C一定在最優(yōu)鏈的末位。即最優(yōu)鏈?zhǔn)?A→B→C)或者(B→A→C)。

雖然首(末)工序定理與重心定理之間不是充分必要關(guān)系，但是滿足首(末)工序定理且位于最優(yōu)鏈?zhǔn)?末)位的工序重心最小(大)?？偨Y(jié)重心定理和首、末工序定理給予的啟示，建立以活動重心為優(yōu)先規(guī)則的，以并行調(diào)度為基礎(chǔ)的，運(yùn)用正反向迭代技術(shù)的兩階段啟發(fā)式算法來進(jìn)行關(guān)鍵鏈的識別(an iterative method for critical chain identifying using activity’s center of gravity as priority rule )。簡單起見，稱之為迭代重心法(I-ACG)。

2　基于活動重心定理的關(guān)鍵鏈識別法-迭代重心法

迭代重心法識別關(guān)鍵鏈包括2個計算階段，第一階段求解RCPSP問題，第二階段在第一階段計算結(jié)果的基礎(chǔ)上進(jìn)行關(guān)鍵鏈的識別。

2.1第一階段——迭代重心法求解RCPSP問題

第一階段計算流程如下：

1) 利用關(guān)鍵路徑法(CPM)求解問題，得到各活動的初始時間參數(shù)ES和LF，利用式(1)計算各活動的重心ACG。

2) 正向-1(Forward1)計算。

采用并行調(diào)度法，由p階段組成，每有工序完成則推進(jìn)到下一階段；在新的時間節(jié)點(diǎn)tp處構(gòu)建3個活動集合Cp，Ap和Sp，分別代表到時間節(jié)點(diǎn)tp止，已完成活動、正在進(jìn)行活動和可調(diào)度活動集合；位于Sp中的活動，其緊前活動已完成，且資源需要量滿足當(dāng)前資源約束條件。

tp=min{FTj|j∈Ap-1},

Ap=Ap-1{j|j∈Ap-1，F(xiàn)Tj=tp},

Cp=Cp-1∪{j|j∈Ap-1，F(xiàn)Tj=tp},

Sp中擁有較小重心的活動優(yōu)先安排；重心相等時，優(yōu)先選擇工期較長的活動；工期相等時，優(yōu)先選擇網(wǎng)絡(luò)編號小的活動。

j*=min{j|v(j)= ACGj，j∈Sp},

ifv(j1)=v(j2) ,thenj*=max{Dj},

ifD(j1)=D(j2),thenj*=min{idj}。

反復(fù)迭代，直到所有的活動都被安排，則當(dāng)前計算結(jié)束，得到各活動滿足執(zhí)行和資源雙重約束的正向-1計劃和正向-1工期(ForwardSchedule1和ForwardDuedate1)。

FTj為活動j的完成時間；K為資源種類；Rk為第k種資源最大可供數(shù)量;rik為活動i所需第k種資源的數(shù)量。

3)反向-1(Backward1)計算。

反向計算仍然從零時刻開始進(jìn)行；不同的是Sp中的活動，其緊后活動都已完成，且資源需要量滿足當(dāng)前資源約束條件。

通過以下關(guān)系聯(lián)系正向-1和反向-1計算,見式(4)和圖1。

LF1j=ForwardDuedate1-ForwardSchedule1j,

LS1j=LF1j-Dj。

(4)

圖1　正向-1計算與反向-1計算關(guān)系

Sp中擁有較小最遲開始時間的活動優(yōu)先安排；最遲開始時間相等時，優(yōu)先選擇編號較小的活動。

j*=min{j|v(j)= LS1j，j∈Sp},

ifv(j1)=v(j2), thenj*=min{idj}。

反復(fù)迭代，直到所有的活動都被安排，則當(dāng)前計算結(jié)束，得到各活動滿足約束的反向-1計劃和反向-1工期(BackwardSchedule1和BackwardDuedate1)。

4)判斷。

a)如果BackwardDuedate1>ForwardDuedate1，則計算終止，正向-1計算中得到的調(diào)度計劃為項(xiàng)目可行計劃，正向-1工期為項(xiàng)目完工期；

b)如果BackwardDuedate1≤ ForwardDuedate1，則繼續(xù)進(jìn)行正向-2計算。

5)正向-2(Forward2)計算。

通過以下關(guān)系聯(lián)系反向-1和正向-2計算：

EF2j=BackwardDuedate1-BackwardSchedule1j,

ES 2j=EF2j-Dj,

(5)

Sp中擁有較小最早開始時間的活動優(yōu)先安排；最早開始時間相等時，優(yōu)先選擇編號較小的活動。

j*=min{j|v(j)= ES2j，j∈Sp},

ifv(j1)=v(j2), thenj*=min{idj}。

反復(fù)迭代，直到所有的活動都被安排，則當(dāng)前計算結(jié)束，得到各活動滿足約束的正向-2計劃和正向-2工期(ForwardSchedule2和ForwardDuedate2)。

6)判斷。

a)如果ForwardDuedate2>BackwardDuedate1，則計算終止，反向-1中得到的調(diào)度計劃為項(xiàng)目可行計劃，反向-1工期為項(xiàng)目完工期；

b)如果ForwardDuedate2≤BackwardDuedate1，則回到第3步，進(jìn)行反向-2計算，計算方法同反向-1計算。

如此反復(fù)進(jìn)行迭代計算，直到項(xiàng)目工期不再改善，則計算終止。迭代重心法第一階段計算流程如圖2所示。

圖2　迭代重心法(I-ACG)第一階段計算流程

2.2第二階段——關(guān)鍵鏈的識別

1)在第一階段迭代計算過程中，如果在兩個迭代方向同時得到最優(yōu)(近優(yōu))工期，即：在某次序迭代得到

ForwardDuedate(m)=BackwardDuedate(m-1),

orBackwardDuedate(m)=ForwardDuedate(m)。

(6)

則正向計算對應(yīng)的計劃為項(xiàng)目最早資源可行時間計劃，反向計算對應(yīng)的計劃為項(xiàng)目最晚資源可行時間計劃。正向計劃與反向計劃中活動的最早開始時間等于最晚開始時間的活動構(gòu)成關(guān)鍵鏈。

2)如果僅在一個迭代方向得到最優(yōu)工期，則按文獻(xiàn)[6]介紹的，用動態(tài)規(guī)劃的思想，對得到的最優(yōu)(較優(yōu))調(diào)度計劃逐步右移、或者左移的啟發(fā)式算法來識別關(guān)鍵鏈和非關(guān)鍵鏈。

流程如下圖3所示。

圖3　迭代重心法(I-ACG)第二階段流程

3　I-ACG算法的驗(yàn)證

3.1驗(yàn)算問題集

本文選用Patterson110問題集作為問題樣本，同時選用Kolisch和?zdamar[17-21]等總結(jié)出的3種表現(xiàn)較好的啟發(fā)式規(guī)則：最小時差(minSlack)，最遲完成時間(minLFT)，最大位置權(quán)重(maxGRPW)進(jìn)行對比研究。Patterson 110問題集從實(shí)踐中收集而來，有10個問題包含51個活動，3種可用資源；8個問題包含的活動數(shù)量少于20個，1～3種可用資源；其它102個問題包含的活動數(shù)介于20～35之間，1～3種可用資源。

3.2計算結(jié)果統(tǒng)計與比較

采用Matlab語言進(jìn)行編程，統(tǒng)計每種優(yōu)先規(guī)則計算方法獲得的完工期與最優(yōu)完工期之間的平均偏離率(Mean)，偏離標(biāo)準(zhǔn)方差(StdDev)及獲得最優(yōu)工期的次數(shù)(OptNum)。公平起見，對其它優(yōu)先規(guī)則也進(jìn)行了迭代運(yùn)算，結(jié)果見表1。

表1　Patterson110問題求解結(jié)果統(tǒng)計

從上表中看到，針對Patterson110問題集，在首次結(jié)算結(jié)果中，迭代重心法計算結(jié)果與最小最遲開始時間得到的最優(yōu)計劃次數(shù)接近，但是與最優(yōu)計劃工期偏離均值與標(biāo)準(zhǔn)差均小于后者；同時這2種優(yōu)先規(guī)則的計算結(jié)果明顯優(yōu)于最小時差和最大位置權(quán)重法計算結(jié)果。

對各種方法進(jìn)行迭代計算后，計算結(jié)果都得到了優(yōu)化，迭代重心法在3項(xiàng)指標(biāo)上的結(jié)果都顯著優(yōu)于其它方法。

對本文方法與其它方法得到的優(yōu)化工期，做基于成對數(shù)據(jù)的單邊t檢驗(yàn)，顯著性水平0.05，樣本值110，t0.05(109)=1.659。結(jié)果如表2所示。

表2　不同方法間的計劃工期假設(shè)檢驗(yàn)計算結(jié)果

從檢驗(yàn)結(jié)果看到，不論是首次計算還是經(jīng)正、反向迭代計算后，I-ACG計算結(jié)果均優(yōu)于其它方法。當(dāng)然，經(jīng)過迭代計算后，結(jié)果的顯著性大大提高。

經(jīng)典RCPSP問題以最小化項(xiàng)目工期為目標(biāo)，由式(1)看到，活動的重心ACG由2倍的活動最早開工時間ES，總時差TF和活動工期的和構(gòu)成，前兩者為時間特性參數(shù)，工期為活動屬性參數(shù)，ACG包含的信息量較其它優(yōu)先規(guī)則豐富。其次，新設(shè)計方法將每次迭代的計算結(jié)果都傳遞到下一次迭代中，使得活動的優(yōu)先值具有動態(tài)性。優(yōu)先規(guī)則信息的豐富性和活動優(yōu)先值的動態(tài)性賦予了I-ACG方法較好地計算結(jié)果。

經(jīng)統(tǒng)計，110個問題中，只有23個問題是在一個方向的迭代中得到最(近)優(yōu)計劃，需要再次利用右移、或者左移計算來求得對應(yīng)的最晚、最早資源可行計劃；其它87個問題可以同時得到最早、最晚資源可行計劃，對比每個活動的最早開始時間與最晚開始執(zhí)行時間，即可得到關(guān)鍵鏈。

4　結(jié)論

在2個平行工序順序化重心定理的啟發(fā)下，本文構(gòu)建了兩階段關(guān)鍵鏈識別的啟發(fā)式算法，第一階段利用活動的重心作為優(yōu)先規(guī)則，運(yùn)用正、反向迭代技術(shù)建立了求解RCPSP問題的迭代重心法(I-ACG)；第二階段在第一階段得到的最優(yōu)或者近優(yōu)計劃基礎(chǔ)上，根據(jù)迭代計算的不同結(jié)果，運(yùn)用活動的時間參數(shù)對比、或者動態(tài)規(guī)劃的方法識別出關(guān)鍵鏈。

以Patterson110問題集為樣本，對I-ACG法和經(jīng)典的3種優(yōu)先規(guī)則進(jìn)行了計算結(jié)果對比，統(tǒng)計數(shù)據(jù)說明本文建立的啟發(fā)式求解RCPSP問題的迭代重心法有一定的先進(jìn)性。而且經(jīng)過正、反向迭代計算，約80%的問題可以同時在兩個計算方向得到最優(yōu)(近優(yōu))解，極大地簡化了關(guān)鍵鏈的識別過程。

當(dāng)然，利用優(yōu)先規(guī)則建立的啟發(fā)式求解RCPSP問題的方法不能同元啟發(fā)式方法和精確算法相比較，但基于優(yōu)先規(guī)則建立的啟發(fā)式算法省時，難度低，易應(yīng)用于商業(yè)軟件并被企業(yè)采納，市場推廣度好；因此不斷完善和挖掘好的優(yōu)先規(guī)則，建立簡單實(shí)用的RCPSP問題求解方法仍具有現(xiàn)實(shí)意義；尤其在迭代計算中大部分問題可以同時在兩個計算方向得到最(近)優(yōu)解，一次計算即可達(dá)到關(guān)鍵鏈識別的目的。

[1]HERROELEN W, DE REYCK B, DEMEULEMEESTER E．Resource-constrained project scheduling：A survey of recent development [J]．Computers and Operations Research ，1998，25(4)：279-302．

[2]BRUCKER P, DREXL A, MOHRING R, et al. Resource-constrained project scheduling：Notation，classification，models and methods [J]．European Journal of Operational Research ，1999，112(1)：3-41．

[3]LEACH L. Schedule and cost buffer sizing: How to account for the bias between Project performance and your model[J]. Project Management Journal, 2003, 34(2):34-47．

[4]TUKEL O I, ROM W O, EKSIOGLU S D. An investigation of buffer sizing techniques in critical chain scheduling[J]. European J of Operational Research, 2006,172 (2):401-416．

[5]莫巨華. 基于關(guān)鍵鏈的項(xiàng)目調(diào)度模型與算法[D]. 沈陽:東北大學(xué)信息科學(xué)與工程學(xué)院, 2005: 16-34．

MO Juhua. Critical chain based models and algorithms for project scheduling[D].Shenyang: College of Information Science and Engineering, Northeastern University ,2005:16-34．

[6]田文迪, 崔南方. 關(guān)鍵鏈項(xiàng)目管理中關(guān)鍵鏈和非關(guān)鍵鏈的識別[J]． 工業(yè)工程與管理, 2009, 14(2): 88-93．

TIAN Wendi, CUI Nanfang. Identifying the critical chain and non-critical chain in the project management[J]. Industrial Engineering and Management ,2009,14(2):88-93.

[7]RABBANI M., GHOMI S M T, JOLAI F, et al. A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept[J]. European Journal of Operational Research, 2007, 176(2):794-808．

[8]管在林, 馬力, 何敏, 等. 基于貢獻(xiàn)度的項(xiàng)目調(diào)度方法研究[J]．計算機(jī)集成制造系統(tǒng), 2008, 14(12): 2431-2435．

GUAN Zailin, MA Li, HE Min, et al. Project scheduling method based on the contribution index[J].Computer Integrated Manufacturing System , 2008, 14(12): 2431-2435．

[9]馬國豐, 尤建新, 杜學(xué)美． 識別關(guān)鍵沖突任務(wù)的定量分析[J]. 上海交通大學(xué)學(xué)報, 2006, 40(4): 668-671．

MA Guofeng, YOU Jianxin, DU Xuemei. Quantitative analysis of identifying critical conflict tasks [J]. Journal of Shanghai Jiaotong University,2006, 40(4): 668-671．

[10]HARTMANN S, BRISKORN D．A survey of variants and extensions of the resource-constrained project scheduling problem[J]．European Journal of Operational Research ，2010，207(1)：1-14．

[11]KOLISH R．Serial and parallel resource constrained project scheduling methods revisited：theory and computation [J]．European Journal of Operational Research，1996，90(2)：320-333．

[12]KLEIN R．Bidirectional planning：improving priority rule-based heuristics for scheduling resource-constrained projects[J]．European Journal of Operational Research，2000，127(3)：619-638．

[13]?ZDAMAR L，ULUSOY G．An iterative local constraints based analysis for solving the resource constrained project scheduling problem[J]．Journal of Operations Management，1996，14(3)：193-208．

[14]LI K Y， WILLS R J．An iterative scheduling technique for resource-constrained Project scheduling[J]．European Journal of Operational Research，1992，56(3)：370-379．

[15]VALLS V，BALLESTIN F，QUINTANILLA S．Justification and RCPSP：a technique that pays[J]．European Journal of Operational Research，2005，165(2)：375-386．

[16]乞建勛，李星梅，王強(qiáng)．CPM網(wǎng)絡(luò)中的路長定理及其在順序優(yōu)化中的應(yīng)用[M]．北京：科學(xué)出版社，2008．

[17]KOLISCH R．Efficient priority rules for the resource-constrained project scheduling problem[J]．Journal of Operations Management，1996，14(3)：179-192．

[18]HARTMANN S, KOLISCH R．Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem[J]．European Journal of Operational Research，2000，127(2)：394-407．

[19]KOLISCH R，HARTMANN S．Experimental investigation of heuristics for the resource-constrained project scheduling：an update[J]．European Journal of Operational Research，2006，174(1)：23-37．

[20]BRUCKER P，KUST S．Complex Scheduling[M]，2006，Springer．

[21]?ZDAMAR L, ULUSOY G. An iterative local constrained based analysis for solving the resource constrained project scheduling problem[J]. Journal of Operations Management, 1996, 14(3): 193-208．

A Critical Chain Identifying Method Based on the Activity′s Center of Gravity Theory

WANG Yi1,2， CUI Nanfang1

(1. School of Management, Huazhong University of Science & Technology, Wuhan 430074, China；2. School of Logistics Engineering, Wuhan University of Technology, Wuhan 430063, China)

Aiming at the critical chain identifying problem, which is the fundamental issue in critical chain project management, a two-stage critical chain identifying heuristic method is introduced based on the theorem of activity′s center of gravity. The well-known Patterson 110 instances are resolved by this new algorithm and three other heuristic methods using different priority rules. Comparing the calculation results by the mathematical statistical hypothesis test method, statistics show that the newly built method is advanced and greatly simplifies the identification of critical chain.

critical chain identifying; activity′s center of gravity; priority rule

2015- 06- 24

國家自然科學(xué)基金資助項(xiàng)目(71271097)；國家青年科學(xué)基金資助項(xiàng)目(71201119).

王藝(1977-)，女，陜西省人，博士研究生，主要研究方向?yàn)樯a(chǎn)運(yùn)作，項(xiàng)目管理.

10.3969/j.issn.1007- 7375.2016.04.010

C935 C94 F272

A

1007-7375(2016)04- 0063- 05