重復(fù)性建設(shè)項目趕工問題

張立輝，　梁洪源

(華北電力大學(xué)　經(jīng)濟與管理學(xué)院， 北京　102206)

?

重復(fù)性建設(shè)項目趕工問題

張立輝，梁洪源

(華北電力大學(xué)經(jīng)濟與管理學(xué)院， 北京102206)

摘要：壓縮正控制子工序的工期，是處理重復(fù)性建設(shè)項目趕工問題的常用手段，但這類方法將產(chǎn)生較大的項目總費用。本文提出了重復(fù)性建設(shè)項目趕工問題新算法。算法為項目中的正控制子工序和逆控制子工序，分別制定相應(yīng)的調(diào)整方案，每一步調(diào)整將挑選出對應(yīng)總費用增加率最小的方案，直至達到預(yù)定的工期，確保項目能以最小的費用實現(xiàn)趕工。此外，本文提供判別控制子工序類別的新方法，用以判定出控制子工序的類別。算例分析結(jié)果顯示，本文算法能簡便識別出各類型控制子工序，并以較小的計算量得到對應(yīng)最小總費用精確解。

關(guān)鍵詞：重復(fù)性項目；控制子工序；項目總工期；趕工

重復(fù)性建設(shè)項目是由多個重復(fù)單元組成的項目，其中的每個單元都具有相同的工作。如高速公路工程、房屋工程、橋梁工程等，需要在多個不同的單元里重復(fù)進行相同的工作，這類建設(shè)項目就屬于重復(fù)性項目。通常情況下，將重復(fù)施工的單元集合稱為工序，工序在某個特定單元的部分稱為子工序[1]。傳統(tǒng)的項目調(diào)度問題，常用關(guān)鍵路徑法(CPM)來解決。但是，當(dāng)處理重復(fù)性項目時，CPM網(wǎng)絡(luò)就會存在許多的不足[2]，主要表現(xiàn)在：(1)難以確保資源的連續(xù)性[3]；(2)無法顯示兩個工序之間的距離約束[4]；(3)各子工序的工作效率無法體現(xiàn)[5]。針對這些不足，常用線性調(diào)度法(LSM)[6]、重復(fù)性調(diào)度法(RSM)[3]以及平衡線法(LOB)[7]等方法處理重復(fù)性項目調(diào)度。本文將使用RSM來表示重復(fù)性項目，該方法在二維坐標(biāo)中用縱軸表示時間，橫軸表示各單元子工序。

處理趕工問題的核心目標(biāo)，是要使得調(diào)整后的項目總工期達到預(yù)定的最晚總工期。由于在所有的CPM網(wǎng)絡(luò)圖中都存在關(guān)鍵路徑，對關(guān)鍵路徑上的工序進行適當(dāng)?shù)膲嚎s，能夠縮短項目的總工期，因此在處理一般項目的趕工問題時，主要采取對CPM網(wǎng)絡(luò)中的關(guān)鍵工序進行工期壓縮的方式。RSM中存在著與CPM的關(guān)鍵路徑相似的路線，稱為控制路線，位于控制路線上的子工序稱為控制子工序。一般情況下，可以將控制子工序分為兩類：正控制子工序和逆控制子工序[1]。對正控制子工序工期進行適當(dāng)壓縮，可以達到減少項目總工期的目的；與之相反，對逆控制子工序工期進行適當(dāng)延長或者引入間斷時間，反而能夠縮短項目總工期。除總工期之外，重復(fù)性項目趕工問題還需要考慮項目的總費用。項目的總費用通?？梢苑纸鉃橹苯淤M用、間接費用以及資源閑置費用。整個項目所有子工序的直接費用總和即為項目的直接費用，每個子工序的工作量及工作效率不同，將導(dǎo)致各子工序的直接費用有所差別。間接費用是間接為項目服務(wù)而產(chǎn)生的費用，通常與總工期成正比例關(guān)系[8]。資源閑置費用由項目停工期間的照常支付的設(shè)備租賃費、勞務(wù)費等組成，通常與間斷時間成正比。

本文探討的重復(fù)性項目趕工問題，是重復(fù)性項目“時間-費用”權(quán)衡中的子問題，其實質(zhì)是在最晚總工期確定的前提下，給出總費用最小的趕工方案。許多學(xué)者曾利用模型規(guī)劃的方法來處理重復(fù)性項目趕工問題。例如，Reda[9]曾提出一個數(shù)學(xué)規(guī)劃模型，該模型以項目總工期早于最晚總工期為條件，以項目總費用最小為目標(biāo)，對趕工問題進行求解。Sonouci等[10]利用動態(tài)規(guī)劃來求解最優(yōu)趕工方案，這類方法需要較大的計算量，不適合大型項目的計算。

隨著計算機應(yīng)用的不斷深入，有許多學(xué)者將人工智能算法應(yīng)用到重復(fù)性項目的趕工問題中。例如，Hegazy等[11]將CPM與LOB相結(jié)合，并利用遺傳算法來搜索優(yōu)化方案。Long等[12]基于遺傳算法，對總工期與總費用之間的不同權(quán)值，給出不同的最優(yōu)趕工方案。Hegazy等[13]則將軟邏輯應(yīng)用到趕工問題中，以求解最優(yōu)方案。通常情況下，智能算法只能得到問題的近似解，而且需要較大的計算量，當(dāng)問題的規(guī)模增大時將面臨較大的求解難度。Hamid等[14]將CPM與LOB相結(jié)合來處理趕工問題，該方法在問題規(guī)模增大的情況下同樣面臨著較大的計算量。Liu等[15]將外包資源引入到重復(fù)性項目調(diào)度中，但該方法實際上只考慮對工序工期進行壓縮，這將產(chǎn)生較大的項目總費用。

本文將首先從理論上分析不同類型的控制子工序?qū)χ貜?fù)性項目總工期的影響，并提出一種能更簡便地判斷出各控制子工序類別的方法。算法為正控制子工序和逆控制子工序分別制定相應(yīng)的調(diào)整方案。每次調(diào)度調(diào)整挑選出總費用增加率最小的方案，能確保最優(yōu)調(diào)度的總費用最小。最后，利用一個橋梁建設(shè)的案例，展示本文算法在處理趕工問題中的優(yōu)勢。

1控制子工序的類型及判定

根據(jù)控制子工序的類別，為其分別提供相應(yīng)調(diào)整方案，是本文算法能否順利進行的關(guān)鍵一步。正確選擇每一步所需調(diào)整的子工序，并對其進行相應(yīng)的調(diào)度調(diào)整，才能確保項目能順利達到趕工目的。為此，本節(jié)將從理論上分析不同類型控制子工序工期的變化對項目總工期和總費用的影響，并提出一種確定控制子工序類別的新方法。

1.1控制子工序的類型

正控制子工序的性質(zhì)類似于CPM網(wǎng)絡(luò)中的正關(guān)鍵子工序，對這類子工序的工期進行適當(dāng)壓縮，在使得該子工序工期縮短的同時，還能縮短項目的總工期[16]。但壓縮子工序工期需要引入更多的資源，將會增加較多項目總費用。在重復(fù)性項目調(diào)度中，當(dāng)某一子工序處于控制路線上，且具有比其緊前子工序和緊后子工序更低的效率時，它就是一個正控制子工序。如圖1所示，b是一個正控制工序，假設(shè)各工序間存在“結(jié)束-開始”時間約束。適當(dāng)壓縮工序b的工期，可使得工序c的開始時間提前，最終導(dǎo)致項目總工期縮短。

圖1　壓縮正控制工序

逆控制子工序是重復(fù)性項目中一種常見的工序，它具有與正控制子工序相反的性質(zhì)，適當(dāng)延長它的工期，反而會縮短項目的總工期[1]。利用逆控制子工序的這一特性，我們可以通過適當(dāng)降低逆控制子工序工作效率的方式，使項目總工期縮短，同時還能減小項目總費用的增加量。在重復(fù)性項目調(diào)度中，當(dāng)某一子工序處于控制路線上，且具有比其緊前子工序和緊后子工序更高的效率時，它就是一個逆控制子工序。如圖2所示，工序b是逆控制工序，假設(shè)各工序間存在“結(jié)束-開始”時間約束。對工序b的工期進行適當(dāng)延遲后，工序b的開始時間可以提前，使得工序c的開始時間提前，最終導(dǎo)致項目總工期縮短。

圖2　延遲逆控制工序

在兩個連續(xù)的逆控制子工序單元之間適當(dāng)引入間斷時間，同樣可以達到縮短項目總工期的效果。如圖3所示，假設(shè)各工序間存在“結(jié)束-開始”時間約束，逆控制工序b包含三個連續(xù)的子工序單元，在工序b之間引入間斷時間，可以使得工序b的開始時間提前，并使得工序c的開始時間提前，最終導(dǎo)致項目總工期縮短。由于引入間斷時間會導(dǎo)致人員及設(shè)備的閑置，這將增加資源閑置費用，從而在一定程度上增加項目總費用。

圖3　逆控制工序中引入間斷時間

1.2控制子工序類型的判別方法

首先要根據(jù)已有方法來確定調(diào)度中的控制路線，處在控制路線上的子工序即為控制子工序[17]。在項目調(diào)度的調(diào)整階段，任何控制子工序的工期變化都有可能導(dǎo)致控制路線發(fā)生改變，使得最終的項目總工期發(fā)生改變。當(dāng)我們搜尋出調(diào)度中的控制路線之后，本小節(jié)將通過對控制路線上每一個子工序與其緊前子工序、緊后子工序的開始時間和結(jié)束時間進行對比計算，求解出每一個控制子工序的V值，并根據(jù)該值的正負性，判定控制子工序的類別。式(1)～(6)將說明如何判定控制子工序的類型。

Li,j=Si,j-Si-1,j

(1)

Ri,j=Fi,j-Fi-1,j

(2)

Vi,j=Ri,j-Li,j

(3)

Li+1,j=Si+1,j-Si,j

(4)

Ri+1,j=Fi+1,j-Fi,j

(5)

Vi+1,j=Ri+1,j-Li+1,j

(6)

式中：Si,j、Si-1,j、Si+1,j為子工序ai,j、ai-1,j、ai+1,j的開始時間；Fi,j、Fi-1,j、Fi+1,j為子工序ai,j、ai-1,j、ai+1,j的結(jié)束時間；Ri,j為子工序ai,j與其緊前工序ai-1,j結(jié)束時間的差值；Ri+1,j為子工序ai,j與其緊后工序ai+1,j結(jié)束時間的差值；Li,j為子工序ai,j與其緊前工序ai-1,j開始時間的差值；Li+1,j為子工序ai,j與其緊后工序ai+1,j開始時間的差值；Vi,j為Ri,j與Li,j的差值；Vi+1,j為Ri+1,j與Li+1,j的差值。

當(dāng)Vij>0且Vi+1,j<0時，可判定ai,j是正控制子工序；當(dāng)Vij<0且Vi+1,j>0時，可判定子工序ai,j是逆控制子工序。特別地，位于第一道工序或最后一道工序上的控制子工序?qū)儆谡刂谱庸ば颉?/p>

圖4呈現(xiàn)了一個典型的重復(fù)性項目，該項目包含5道工序，每道工序內(nèi)有4個單元的子工序。圖中加粗部分為該調(diào)度的控制路線。對于子工序a2,1，由于該子工序處于控制路線上，且V2,1<0，V3,1>0，我們可以判定：子工序a2,1為逆控制子工序；對于子工序a3,3，由于該子工序處于控制路線上，且V3,3>0，V4,3<0，我們可以判定子工序a3,3為正控制子工序。

圖4　子工序類型判別

2總費用增加率計算方法

在實際工程中，趕工問題不僅要使項目總工期滿足小于最晚工期的要求，還需要對調(diào)度改變所引起的項目總費用變化進行思考。通常情況下，項目總費用由直接費用和間接費用以及閑置資源費用構(gòu)成。直接費用一般包含材料費用、勞工費、設(shè)備費用等，本文將各子工序的材料費用、勞工費、設(shè)備費用等各費用整合為各子工序的直接費用。間接費用則與項目總工期成正比。每道工序的閑置資源費用則與該工序的間斷時間總和成正比，所有工序的閑置資源費用總和即為項目的閑置資源費用。項目總費用可由式(7)～(10)計算。

(7)

IC=T×ICR

(8)

IRC=IT×IRCRi

(9)

TC=DC+IC+IRC

(10)

式中：DCi,j為子工序ai,j的直接費用；DC為項目的直接費用；IC為項目的間接費用；T為項目總工期；ICR為間接費用率；IRCRi為第i道工序的閑置資源費用率；IT為項目的間斷時間總和；IRC為項目的閑置資源費用；TC為項目總費用。

在趕工過程中，當(dāng)對控制子工序ai,j進行適當(dāng)調(diào)整時，該項目的直接費用、間接費用以及資源閑置費用將可能發(fā)生改變。產(chǎn)生的新調(diào)度方案所對應(yīng)的各項費用計算方法如式(11)～(14)所示。由于項目總費用的計算量主要產(chǎn)生于子工序直接費用累加的過程，因此，通過疊加增量的方式求解新方案直接費用，能在一定程度上減小計算復(fù)雜度。

DCn=DC+ΔDCi,j

(11)

ICn=Tn×ICR

(12)

IRCn=IRC+ΔIT×IRCRi

(13)

TCn=DCn+ICn+IRCn

(14)

式中：DCn為新調(diào)度方案的直接費用；ΔDCi,j為子工序ai,j直接費用的增加量；ICn為新調(diào)度方案的間接費用；Tn為新調(diào)度方案總工期；ΔIT為間斷時間增加量；IRCn為新調(diào)度方案的閑置資源費用率；TCn為新調(diào)度方案的項目總費用。

式(15)給出了總費用增加率的計算方式，該值越小，意味著項目趕工的代價越小，該調(diào)度調(diào)整方案的可接受性就越強。

Ω=(TCn-Tn)/(T-Tn)

(15)

式中：Ω為總費用增加率。

3重復(fù)性項目趕工問題新算法

重復(fù)性項目的趕工問題是指：某一重復(fù)性項目的初始調(diào)度項目總工期為T，由于項目各方的要求，項目需要在D時刻(最晚工期)之前完工。因此，需要通過對初始調(diào)度進行調(diào)整，使得項目總工期T滿足式(16)的要求。

T≤D

(16)

趕工算法需要解決的問題是：對于給定的不滿足最晚工期要求的初始調(diào)度，確定具體的趕工方案，使得最終的調(diào)度在滿足式(16)的前提下，達到項目總費用最小的目標(biāo)。

3.1算法思想

圖5展示了本文算法的總體思想，算法著重利用正控制子工序與逆控制子工序的特性，對項目進行有針對性的調(diào)度調(diào)整。相對于已有的算法，本文算法能以較小的計算量得到趕工問題的精確解，且求得的最優(yōu)調(diào)度所對應(yīng)的項目總費用也最小。

圖5　本文算法總體思想

新算法以迭代運算的方式進行調(diào)度調(diào)整，每一次迭代將單獨對項目中的某一個控制子工序進行調(diào)整。在每一次迭代中，首先利用本文提供的方法，判定出最新調(diào)度控制路線上的每一個控制子工序的類別。緊接著，算法對最新調(diào)度內(nèi)的每一個正控制子工序的工期，在不超過其最短工期的范圍內(nèi)分別進行所有可行的加速調(diào)整，保留能使總工期減小的方案；對最新調(diào)度的每一道逆控制子工序，在不超過其最長工期的范圍內(nèi)分別進行所有可行的延長調(diào)整，保留能使總工期減小的方案；對最新調(diào)度中兩個連續(xù)的逆控制子工序，在不超過最大間斷時間的范圍內(nèi)，在兩者之間引入所有可行的間斷時間，保留所有能使總工期減小的方案。最后，結(jié)合文中提出的總費用增加率Ω的計算方法，從被保留的調(diào)整方案中，挑選出對應(yīng)項目總費用增加率最小的方案，并將該方案存儲為最新調(diào)度，本步迭代調(diào)整完成。

算法重復(fù)進行上述迭代運算，直至最晚工期達成。由于控制子工序的數(shù)量是有限的，而且每一個子工序可供調(diào)整的方案也是有限的，因此，單獨針對每一道控制子工序進行每一步迭代調(diào)整，使得項目能以較小的計算量求解出最優(yōu)趕工調(diào)度方案。

3.2算法步驟

圖6是本文算法的流程圖，具體步驟總結(jié)如下：

(1)初始化，輸入信息，將初始調(diào)度存儲為最新調(diào)度。

(2)查找最新調(diào)度中的控制路線，計算最新調(diào)度中各控制子工序的V值，由此判別出控制子工序的類型，進入(3)。

(3)判斷是否存在工期大于最短工期的正控制子工序(可加速的正控制子工序)，或者工期小于最長工期的逆控制子工序(可延遲的逆控制子工序)，或者間斷時間小于最大間斷時間的兩個相鄰的逆控制子工序(可間斷的逆控制子工序)。若是，進入(4)；若否，進入(8)。

(4)對可壓縮的正控制子工序，在不小于其最短工期的范圍內(nèi)，分別進行所有可行的壓縮調(diào)整；對可延長的逆控制子工序，在不大于其最長工期的范圍內(nèi)，分別進行所有可行的延長調(diào)整；對可間斷的逆控制子工序，分別引入所有可行的間斷時間。轉(zhuǎn)入(5)。

(5)判斷步驟(4)中是否存在能使總工期減小的方案，若是，保留所有能使總工期減小的調(diào)整方案，進入(6)；若否，進入(8)。

(6)分別計算所有保留方案的總費用增加率，挑選出對應(yīng)總費用增加率最小的方案，存儲為最新調(diào)度。進入(7)。

(7)判斷項目總工期是否小于最晚工期。若是，則轉(zhuǎn)入(8)；若否則轉(zhuǎn)入(1)。

(8)調(diào)整結(jié)束，輸出最優(yōu)調(diào)度。

圖6　算法流程

3.3算法優(yōu)勢

相比較于已有的算法，本文算法在處理重復(fù)性項目趕工問題時具備如下優(yōu)勢：

(1)利用文中提出的方法，能簡便的識別出項目中存在的正控制子工序和逆控制子工序。在調(diào)度調(diào)整時，為正控制子工序和逆控制子工序提供相應(yīng)的調(diào)整方案，使得調(diào)整更具針對性。

(2)由于項目中的正控制子工序和逆控制子工序數(shù)量是有限的，且各子工序可供選擇的調(diào)整方案也是有限的，因此，相比較于傳統(tǒng)的對所有工序分別進行壓縮再挑選的方法，本文算法計算量較小，且能得到精確解。

(3)直接調(diào)整控制子工序工期的方式較為直觀，便于項目調(diào)度人員理解。調(diào)度人員可以靈活的運用各種措施，來實現(xiàn)最優(yōu)調(diào)度方案。

4算例分析

本文用一橋梁建設(shè)項目案例來說明新算法的優(yōu)勢。該項目共由五道工序組成：打樁(A)、路基修建(B)、橋墩建設(shè)(C)、主梁(D)、橋面鋪設(shè)(E)，如圖7所示，每道工序都包含四個單元的子工序，同一工序內(nèi)的不同子工序工作量略有不同，各工序之間存在“結(jié)束-開始”約束關(guān)系，同一工序內(nèi)的相鄰兩個單元的子工序至少需要1 d的時間間隔。

圖7　橋梁建設(shè)項目

4.1算法優(yōu)化結(jié)果

表1給出每個子工序的不同工期所對應(yīng)的直接費用，項目的間接費用率為800元/d。表2給出了各道工序內(nèi)相鄰兩個子工序之間的最大間斷天數(shù)，以及每道工序的閑置資源費用率。表3給出了各工序的所有子工序初始調(diào)度的工期，并為各子工序提供工期調(diào)整的變化范圍，當(dāng)某個子工序需要調(diào)整時，可以在最短工期到最長工期之間選擇調(diào)整(這里規(guī)定各子工序工期只能取整)。通過計算，得到項目初始調(diào)度總工期為145 d，初始調(diào)度總費用為1586640元。

表1　子工序不同的工期所對應(yīng)的直接費用　元

表2　各工序允許的最大間斷時間及閑置資源費用率

表3　各子工序初始調(diào)度工期及其最短和最長調(diào)整工期

由于投資方的要求，項目必須在130 d之內(nèi)完工，因此需要對項目進行趕工。利用本文算法對項目進行趕工計算，針對不同的控制子工序類型采取相應(yīng)調(diào)整措施，得到最優(yōu)調(diào)度的項目總工期為130 d，剛好滿足業(yè)主要求，最優(yōu)調(diào)度所對應(yīng)的項目總費用為1679650元。圖8為初始調(diào)度與利用本文算法求得的最優(yōu)調(diào)度之間的對比。

表4給出了本文算法趕工優(yōu)化結(jié)果。通過表4可以發(fā)現(xiàn)，本文算法在趕工的過程中，共進行了9步迭代調(diào)整，分別對A①、A②、A③、A④、C①等五個正控制子工序進行了工期壓縮，對B②、D②、D③等三個正控制工序進行工期延遲，并在D②、D③之間引入了1 d的間斷時間。經(jīng)過如上調(diào)整，使得工期較之初始調(diào)度在縮短10.34%的同時，項目總費用僅僅增加了5.86%。此外，本文算法計算量較小，利用MATLAB軟件處理本例題計算時，用時不到1 s即可得到精確解。

圖8　調(diào)度對比

d

4.2與傳統(tǒng)算法相比較

若使用傳統(tǒng)趕工方法，即壓縮子工序工期的手段，在調(diào)整過程中僅考慮對正控制子工序進行壓縮，每一步調(diào)整挑選對應(yīng)總費用增加率最小的調(diào)整方案，逐步調(diào)整直至達到最晚工期的要求。

調(diào)度調(diào)整結(jié)果如表5所示，通過分析表格數(shù)據(jù)可以發(fā)現(xiàn)，傳統(tǒng)算法在趕工的過程中，僅僅對A①、A②、A③、A④、C①、C②、C③等七個正控制子工序進行了工期壓縮，不考慮其他方式。最終達到130天的工期要求時，所對應(yīng)的最優(yōu)調(diào)度總費用為1750460元，較之初始調(diào)度增加了163820元。由此可見，本文算法著重利用不同類型的控制子工序?qū)椖靠偣て诘挠绊懀沟每偣て谠诳s短15天的同時，比傳統(tǒng)壓縮正控制子工序的方法節(jié)省了70810元，總費用增加量減少近一半。

表5　本文算法與傳統(tǒng)算法對比　d

5結(jié)束語

趕工問題是重復(fù)性建設(shè)項目調(diào)度中的一類常見問題。由于重復(fù)性項目調(diào)度中的控制子工序嚴重影響著項目總工期，因此，本文著重利用此關(guān)系，構(gòu)造趕工問題的新算法，使得項目能在達到合同工期的同時，最大程度地減小項目總費用。文中首先從理論上分析了控制子工序?qū)χ貜?fù)性項目總工期的影響，針對正控制子工序和逆控制子工序提出了不同的趕工策略。并提出了一種新的確定控制子工序類別的方法，該方法能更簡便地判斷出控制路線上各子工序的類別。判別出各子工序的類別之后，本文算法分別對控制路線上的各類型控制子工序進行有針對性的調(diào)整。每一步調(diào)整將挑選出總費用增加率最小的趕工方案，從而確保項目能以最小的總費用達到趕工的目的。最后，利用一個橋梁建設(shè)案例，展示本文算法能以較小的計算量和最小的總費用求得最優(yōu)調(diào)度的優(yōu)勢。由于控制子工序?qū)χ貜?fù)性建設(shè)項目的工期和費用有著重要的影響，筆者將在今后加強對控制子工序的研究。

參考文獻

[1]張立輝, 鄒鑫. 重復(fù)性項目調(diào)度理論與方法研究[M]. 北京： 中國電力出版社，2012.

[2]Selinger S. Construction planning for linear scheduling optimization[J]. Journal of Construction Division, 1980，106(2)： 195-205.

[3]Harris R B，Ioannou P G. Scheduling projects with repeating activities[J]. Journal of Construction Engineering and Management，1998，124(4)： 269-278.

[4]Kallantzis A，Lambropoulos S. Correspondence of activity relationships and critical path between time-location diagrams and CPM[J]. Operational Research，2004，4(3)： 277-290.

[5]Kallantzis A，Soldatos J，Lambropoulos S. Linear versus network scheduling: a critical path comparison[J]. Journal of Construction Engineering and Management，2007，133(7)： 483-491.

[6]Johnston D W. Linear scheduling method for highway construction[J]. Journal of the Construction Division，1981，107(2)： 247-261.

[7]Lumsdem P. The Line-of-balance Method[M]. Oxford：Pegamon Press，1968.

[8]Hyari K H，El-Rayes K, El-Mashaleh M. Automated trade-off between time and cost in planning repetitive construction projects[J]. Construction Management and Economics，2009，27(8)： 749-761.

[9]Reda P M. PRM: repetitive project modeling[J]. Journal of Construction Engineering and Management, 1990，116(2)： 316-330.

[10]Senouci A B, Eldin N N. Dynamic programming approach to scheduling of non-serial linear project[J]. Journal of Construction in Civil Engineering，1996，10(2)： 106-114.

[11]Hegazy T, Wassef N. Cost optimization in projects with repetitive non-serial activities[J]. Journal of Construction Engineering and Management，2001，127(3)： 183-191.

[12]Long L D，Ohsato A. A genetic algorithm-based method for scheduling repetitive construction projects[J]. Automation in Construction，2009，18(4)： 499-511.

[13]Hegazy T，Elhakeem A，Elbeltagi E. Distributed scheduling model for infrastructure networks[J]. Journal of Construction Engineering and Management，2004，130(2)： 160-167.

[14]Hamid R Z D，Abbas A，Reza A. CPM/LOB scheduling method for project deadline constraint satisfaction[J]. Automation in Construction，2014，48： 107-118.

[15]Liu S S，Wang C J. Optimization model for resource assignment problems of linear construction projects[J]. Automation in Construction，2007，16： 460-473.

[16]李星梅，乞建勛，蘇志雄. 自由時差定理與k階次關(guān)鍵路線的求法[J]. 管理科學(xué)學(xué)報，2009，12(2)： 98-104.

[17]張立輝，鄒鑫，乞建勛，等. 重復(fù)性建設(shè)項目中確定關(guān)鍵路線的方法研究[J]. 運籌與管理，2015，1(24)： 142-148.

Repetitive Construction Project Deadline Constraint Satisfaction Problem

ZHANGLi-hui,LIANGHong-yuan

(School of Economics and Management, North China Electric Power University, Beijing 102206, China)

Abstract:Compressing forward controlling segment’s duration is the common method to achieve the desired duration, however, it will have a large total project cost. A new algorithm for repetitive construction project to achieve the desired duration is proposed. The algorithm provides different scheduling adjustment plans for forward controlling segments and backward controlling segments. Every adjustment execution the plan which corresponding to the minimum total cost increase rate, until the desired duration is achieved, it can guarantee the total cost is minimum. In addition, a simple method to find the controlling segments is proposed. Example analysis shows the new algorithm can easily recognize the controlling segments, and obtain an exact solution with a small amount of calculation, meanwhile, the total cost of the optimal solution is smaller than the common algorithm.

Key words：repetitive construction project; controlling segment; project duration; deadline constraint satisfaction

收稿日期：2015-12-10修回日期： 2016-01-22

作者簡介：張立輝(1974-)，男，湖南寧鄉(xiāng)人，教授，博士，研究方向為項目調(diào)度與優(yōu)化(Email：lhy15749@163.com)

基金項目：國家自然科學(xué)基金(71271081)

中圖分類號：TU72

文獻標(biāo)識碼：A

文章編號：2095-0985(2016)03-0022-08