張立輝，　梁洪源

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

?

重復(fù)性建設(shè)項(xiàng)目趕工問(wèn)題

張立輝，梁洪源

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

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

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

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

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

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

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

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

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

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

1.1控制子工序的類型

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

圖1　壓縮正控制工序

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

圖2　延遲逆控制工序

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

圖3　逆控制工序中引入間斷時(shí)間

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

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

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的開始時(shí)間；Fi,j、Fi-1,j、Fi+1,j為子工序ai,j、ai-1,j、ai+1,j的結(jié)束時(shí)間；Ri,j為子工序ai,j與其緊前工序ai-1,j結(jié)束時(shí)間的差值；Ri+1,j為子工序ai,j與其緊后工序ai+1,j結(jié)束時(shí)間的差值；Li,j為子工序ai,j與其緊前工序ai-1,j開始時(shí)間的差值；Li+1,j為子工序ai,j與其緊后工序ai+1,j開始時(shí)間的差值；Vi,j為Ri,j與Li,j的差值；Vi+1,j為Ri+1,j與Li+1,j的差值。

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

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

圖4　子工序類型判別

2總費(fèi)用增加率計(jì)算方法

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

(7)

IC=T×ICR

(8)

IRC=IT×IRCRi

(9)

TC=DC+IC+IRC

(10)

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

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

DCn=DC+ΔDCi,j

(11)

ICn=Tn×ICR

(12)

IRCn=IRC+ΔIT×IRCRi

(13)

TCn=DCn+ICn+IRCn

(14)

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

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

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

(15)

式中：Ω為總費(fèi)用增加率。

3重復(fù)性項(xiàng)目趕工問(wèn)題新算法

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

T≤D

(16)

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

3.1算法思想

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

圖5　本文算法總體思想

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

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

3.2算法步驟

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

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

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

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

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

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

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

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

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

圖6　算法流程

3.3算法優(yōu)勢(shì)

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

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

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

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

4算例分析

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

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

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

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

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

表2　各工序允許的最大間斷時(shí)間及閑置資源費(fèi)用率

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

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

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

圖8　調(diào)度對(duì)比

d

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1]張立輝, 鄒鑫. 重復(fù)性項(xiàng)目調(diào)度理論與方法研究[M]. 北京： 中國(guó)電力出版社，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]李星梅，乞建勛，蘇志雄. 自由時(shí)差定理與k階次關(guān)鍵路線的求法[J]. 管理科學(xué)學(xué)報(bào)，2009，12(2)： 98-104.

[17]張立輝，鄒鑫，乞建勛，等. 重復(fù)性建設(shè)項(xiàng)目中確定關(guān)鍵路線的方法研究[J]. 運(yùn)籌與管理，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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金(71271081)

中圖分類號(hào)：TU72

文獻(xiàn)標(biāo)識(shí)碼：A

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