王　藝， 崔南方

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

?

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

王藝1,2， 崔南方1

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

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

關(guān)鍵鏈識(shí)別； 活動(dòng)重心； 優(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ù)來(lái)保護(hù)關(guān)鍵鏈，從而實(shí)現(xiàn)在動(dòng)態(tài)環(huán)境中保護(hù)項(xiàng)目整體的思想，是關(guān)鍵鏈項(xiàng)目管理方法顯著區(qū)別于現(xiàn)有項(xiàng)目管理技術(shù)，并受到持續(xù)推崇的根本原因。

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

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

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

1　活動(dòng)的重心及重心定理

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

1.1.1活動(dòng)的重心

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

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

(1)

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

1.1.2n元序鏈虧值定理

當(dāng)n個(gè)平行工序A1，A2，…，An調(diào)整為順序工序，即A1→A2→…→An時(shí)，稱后者為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ò)下活動(dòng)的最晚開(kāi)始時(shí)間。

1.1.3重心定理

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

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

[首工序定理] 若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é)重心定理和首、末工序定理給予的啟示，建立以活動(dòng)重心為優(yōu)先規(guī)則的，以并行調(diào)度為基礎(chǔ)的，運(yùn)用正反向迭代技術(shù)的兩階段啟發(fā)式算法來(lái)進(jìn)行關(guān)鍵鏈的識(shí)別(an iterative method for critical chain identifying using activity’s center of gravity as priority rule )。簡(jiǎn)單起見(jiàn)，稱之為迭代重心法(I-ACG)。

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

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

2.1第一階段——迭代重心法求解RCPSP問(wèn)題

第一階段計(jì)算流程如下：

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

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

采用并行調(diào)度法，由p階段組成，每有工序完成則推進(jìn)到下一階段；在新的時(shí)間節(jié)點(diǎn)tp處構(gòu)建3個(gè)活動(dòng)集合Cp，Ap和Sp，分別代表到時(shí)間節(jié)點(diǎn)tp止，已完成活動(dòng)、正在進(jìn)行活動(dòng)和可調(diào)度活動(dòng)集合；位于Sp中的活動(dòng)，其緊前活動(dòng)已完成，且資源需要量滿足當(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中擁有較小重心的活動(dòng)優(yōu)先安排；重心相等時(shí)，優(yōu)先選擇工期較長(zhǎng)的活動(dòng)；工期相等時(shí)，優(yōu)先選擇網(wǎng)絡(luò)編號(hào)小的活動(dòng)。

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)都被安排，則當(dāng)前計(jì)算結(jié)束，得到各活動(dòng)滿足執(zhí)行和資源雙重約束的正向-1計(jì)劃和正向-1工期(ForwardSchedule1和ForwardDuedate1)。

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

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

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

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

LF1j=ForwardDuedate1-ForwardSchedule1j,

LS1j=LF1j-Dj。

(4)

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

Sp中擁有較小最遲開(kāi)始時(shí)間的活動(dòng)優(yōu)先安排；最遲開(kāi)始時(shí)間相等時(shí)，優(yōu)先選擇編號(hào)較小的活動(dòng)。

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

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

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

4)判斷。

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

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

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

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

EF2j=BackwardDuedate1-BackwardSchedule1j,

ES 2j=EF2j-Dj,

(5)

Sp中擁有較小最早開(kāi)始時(shí)間的活動(dòng)優(yōu)先安排；最早開(kāi)始時(shí)間相等時(shí)，優(yōu)先選擇編號(hào)較小的活動(dòng)。

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

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

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

6)判斷。

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

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

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

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

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

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

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

orBackwardDuedate(m)=ForwardDuedate(m)。

(6)

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

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

流程如下圖3所示。

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

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

3.1驗(yàn)算問(wèn)題集

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

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

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

表1　Patterson110問(wèn)題求解結(jié)果統(tǒng)計(jì)

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

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

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

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

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

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

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

4　結(jié)論

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

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

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

[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]. 沈陽(yáng):東北大學(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)鍵鏈的識(shí)別[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ì)算機(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]馬國(guó)豐, 尤建新, 杜學(xué)美． 識(shí)別關(guān)鍵沖突任務(wù)的定量分析[J]. 上海交通大學(xué)學(xué)報(bào), 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ò)中的路長(zhǎng)定理及其在順序優(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(71271097)；國(guó)家青年科學(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