張立輝, 戴谷禹, 鄒 鑫, 乞建勛

(1.華北電力大學(xué) 經(jīng)濟與管理學(xué)院,北京 102206; 2.華北電力大學(xué) 經(jīng)濟管理系,河北 保定 071003)

0 引言

重復(fù)性項目是指在工程的各個單元和工序之間不斷重復(fù)進行施工的一類工程項目[1]，包括公路、管道、橋梁和高層建筑等，涵蓋了絕大多數(shù)的工程建設(shè)項目。由于重復(fù)性項目建設(shè)周期長且投資總量大，有效的計劃和調(diào)度對于該類項目的順利建設(shè)具有十分重要的意義[2]。關(guān)鍵路線法(critical path method, CPM)雖然是最常用的項目調(diào)度工具[3]，但在處理重復(fù)性項目時卻存在許多不足，例如無法保證工作連續(xù)性、無法調(diào)度多工作隊、更新繁瑣等[4,5]。因此，現(xiàn)有研究提出了一些更適用的調(diào)度方法，如平衡線法(LOB，Line of Balance)[6]、線性調(diào)度法(LSM，Linear Scheduling Method)[7]和重復(fù)性調(diào)度法(RSM，repetitive scheduling method)[8]等。其中LOB方法最為常用，該方法采用時間和位置兩個坐標(biāo)將重復(fù)性項目表述為一個二維圖示，以便項目管理者對進度計劃的實際控制。

截止日期問題是重復(fù)性項目調(diào)度研究中最受關(guān)注的問題之一，其旨在不超過給定截止日期前提下求得一個項目工作隊雇傭總量最小的調(diào)度方案[9,10]?，F(xiàn)有研究在LOB方法框架下設(shè)計了一系列有效的截止日期問題求解算法，如CPM/LOB[11]，RUSS[12]，ALISS[13]，HLOB[9]和SHLOB[9]。其中，CPM/LOB方法結(jié)合了CPM和LOB各自的特點，旨在快速生成一個滿足截止日期約束的調(diào)度方案；RUSS和ALISS方法通過不斷調(diào)整工序的工作隊數(shù)量來生成有效的截止日期問題進度計劃；HLOB和SHLOB方法則在搜索過程中增加了尋優(yōu)策略。文獻[10]通過模擬仿真比較了上述幾種方法之間求解效果的差異。還有一些研究則將LOB截止日期問題建立為整數(shù)規(guī)劃模型進行求解[9，14]。

上述研究中的方法大多為啟發(fā)式方法，能夠獲得一個較優(yōu)的調(diào)度方案，但通常不能得到精確的最優(yōu)解。由于重復(fù)性項目往往為大型工程項目，一個準(zhǔn)確的最優(yōu)進度方案能夠節(jié)省大量成本，而目前關(guān)于截止日期問題精確算法的研究仍然空缺。另外，上述研究缺少對截止日期問題性質(zhì)的關(guān)注，在設(shè)計求解方法時未能充分利用問題的結(jié)構(gòu)特征，導(dǎo)致算法求解效率和效果不夠理想。

關(guān)鍵路線是項目調(diào)度的基礎(chǔ)，許多調(diào)度優(yōu)化方法都是以關(guān)鍵路線為基礎(chǔ)設(shè)計的。為了區(qū)別于傳統(tǒng)的關(guān)鍵路線，通常將能夠決定重復(fù)性項目總工期的工序稱為控制工序[7]。相對于關(guān)鍵工序，重復(fù)性項目中的控制工序具有一些獨特的性質(zhì)，例如一些控制工序工期延長但項目總工期反而縮短。為此，文獻[15，16]等依據(jù)控制工序?qū)椖靠偣て诘挠绊懸?guī)律，將控制工序分為正控制工序、逆控制工序和點控制工序三種類型。在控制工序性質(zhì)的影響下，許多重復(fù)性項目調(diào)度優(yōu)化問題能夠表現(xiàn)出一定的規(guī)律性結(jié)構(gòu)特征，如最短工期問題[17]、資源均衡問題[18]和網(wǎng)絡(luò)分析問題[19]等，從而有助于制定更有效的調(diào)度策略。

基于上述研究背景，本文考慮從控制工序性質(zhì)出發(fā)，在LOB方法框架下分析重復(fù)性項目截止日期問題的內(nèi)在結(jié)構(gòu)特征，并以此為依據(jù)設(shè)計高效的調(diào)度優(yōu)化精確算法，最后通過案例分析驗證理論方法的有效性。

1 基于LOB的截止日期問題模型

1.1 LOB表述

作為一種基于圖形的調(diào)度方法，LOB通常采用如圖1所示的二維平面來表述一個重復(fù)性項目的進度計劃[2]。其中，橫縱坐標(biāo)分別代表單元和時間，工序則采用一個向右傾斜的四邊形表示。同時，每一個工序又是由多個工期相同的單元組成，每個單元則由一個小矩形表示。以高層建筑項目為例，建筑的裝修工作可視為一道工序，則每一層的裝修工作可視為該工序的一個單元。

圖1 LOB圖示

執(zhí)行速率 在重復(fù)性項目中，一個工序通常會同時雇傭多個工作隊進行施工，為了保證工作隊施工過程的連續(xù)，所有單元需按一定的順序分配給工作隊執(zhí)行，工作隊則需要在不同的單元之間輪轉(zhuǎn)施工。對任意工序i，其執(zhí)行速率ri與單元工期di以及雇傭的工作隊數(shù)量xi應(yīng)滿足如下關(guān)系：

ri=xi/di

(1)

基于工序的執(zhí)行速率，工序內(nèi)各個單元的開始時間則由式(2)聯(lián)系起來。

(2)

其中sij表示第i個工序在第j個單元的開始時間。

確定所有工序的工作隊雇傭數(shù)量后，可根據(jù)工序間的優(yōu)先關(guān)系構(gòu)建完整的LOB進度計劃。

1.2 截止日期問題模型

重復(fù)性項目的截止日期問題旨在滿足截止日期的前提下求得一個工作隊雇傭總量最小的調(diào)度方案。本文根據(jù)文獻[14]對截止日期問題的描述，構(gòu)建其數(shù)學(xué)優(yōu)化模型。該問題的目標(biāo)即為最小化項目工作隊雇傭數(shù)量，如式(3)所示，其中m表示項目的工序數(shù)量。

(3)

優(yōu)先關(guān)系約束保證了重復(fù)性項目的工序在施工過程中不會發(fā)生沖突，即一個工序的某一個單元完成后，該單元上的緊后工序才能開始。式(4)表述了這種優(yōu)先關(guān)系約束，其中sik表示工序i在單元k上的開始時間，sjk表示工序i的緊后工序j在單元k上的開始時間。

sik+di≤sjk

(4)

截止日期約束確保項目在指定的截止日期Td內(nèi)完工。由于重復(fù)性項目的總工期通常由最后一個單元的完成時間控制，因此，截止日期約束可如式(5)所示，其中n表示項目的單元數(shù)量。

smn+dm≤Td

(5)

通常情況下，重復(fù)性項目的建設(shè)存在資源約束限制，即每個工序雇傭的工作隊數(shù)量應(yīng)有上限。該約束如式(6)所示，其中upi表示工序i的工作隊雇傭數(shù)量上限。

xi≤upi

(6)

2 截止日期問題性質(zhì)

2.1 控制工序類型與性質(zhì)

在CPM中，關(guān)鍵工序的性質(zhì)都是相同的，即延長或縮短任意關(guān)鍵工序，項目總工期也會相應(yīng)地發(fā)生延長或縮短。但在重復(fù)性項目，不同類型控制工序的工期變化對項目總工期的影響卻并不相同。在文獻[15]的基礎(chǔ)上，本文考慮將控制工序分為正控制工序、逆控制工序、開始控制工序和結(jié)束控制工序四種類型。

圖2(a)和圖2(b)中的工序j分別代表了典型的正控制工序和逆控制工序，工序i和k則代表了工序j的緊前控制工序和緊后控制工序。正控制工序的特點是與其緊前控制工序的優(yōu)先關(guān)系約束僅在第1個單元處嚴格成立，即sj1=fi1，其中sj1表示工序j在第1個單元處的開始時間，fi1表示工序i在第1個單元處的結(jié)束時間。同時，正控制工序與其緊后控制工序的優(yōu)先關(guān)系僅在最后一個單元處嚴格成立，即fjn=skn。同樣，逆控制工序的特點則是與其緊前控制工序的優(yōu)先關(guān)系約束在最后一個單元處嚴格成立，即sjn=fin，與其緊后控制工序的優(yōu)先關(guān)系在第一個單元處嚴格成立，即fj1=sk1。

圖2 正控制工序和逆控制工序

文獻[15]將工序工期變化對項目總工期沒有影響的控制工序定義為點控制工序，本文根據(jù)優(yōu)先關(guān)系的不同進一步將點控制工序分為開始控制工序與結(jié)束控制工序。其中，開始控制工序的特點是與其緊前控制工序和緊后控制工序的優(yōu)先關(guān)系都在第一個單元處嚴格成立，即sj1=fi1且fj1=sk1，如圖3(a)所示。結(jié)束控制工序的特點是與其緊前控制工序和緊后控制工序的優(yōu)先關(guān)系都在最后一個單元處嚴格成立，即sjn=fin且fjn=skn，如圖3(b)所示。

圖3 開始控制工序和結(jié)束控制工序

根據(jù)上述各類控制工序的特點可以發(fā)現(xiàn)，優(yōu)先關(guān)系嚴格成立的單元不變的前提下，在一定范圍內(nèi)改變控制工序的執(zhí)行速率不會導(dǎo)致控制工序自身類型發(fā)生變化。其中，正控制工序的執(zhí)行速率在[1/dj,ri]內(nèi)變化不會導(dǎo)致自身轉(zhuǎn)變?yōu)槠渌愋偷目刂乒ば颍婵刂乒ば驁?zhí)行速率的變化區(qū)間為[ri,upj/dj]，開始控制工序執(zhí)行速率的變化區(qū)間為[rk,ri]，結(jié)束控制工序執(zhí)行速率的變化區(qū)間則為[ri,rk]。

2.2 工序性質(zhì)與總工期關(guān)系

根據(jù)文獻[15]，重復(fù)性項目的總工期可由式(7)計算。

(7)

其中Di表示工序i的工期，I1表示正控制工序集合，I2表示逆控制工序集合，I3表示開始控制工序集合，I4表示結(jié)束控制工序集合。

單個工序i的工期Di可由該工序的單元數(shù)和執(zhí)行速率計算得到，如式(8)所示。

(8)

將式(8)帶入式(7)中，可得到基于工序執(zhí)行速率的重復(fù)性項目總工期公式，如式(9)所示。

(9)

控制工序的特點表明控制工序的執(zhí)行速率在一定范圍內(nèi)變化時其自身類型不變，而項目總工期公式(9)則反映了控制工序執(zhí)行速率與總工期之間的關(guān)系。結(jié)合二者可以得到關(guān)于控制工序執(zhí)行速率與項目總工期關(guān)系的命題：

命題1若工序j為正控制工序，當(dāng)工序執(zhí)行速率rj在[1/dj,ri]內(nèi)變化時，增加工序執(zhí)行速率rj，項目總工期減少，減少工序執(zhí)行速率rj，項目總工期的增加。

證明若工序j為正控制工序，由正控制工序性質(zhì)，其執(zhí)行速率rj在區(qū)間[1/dj,ri]內(nèi)變化時不改變自身工序類型。由式(9)可知，執(zhí)行速率在該區(qū)間內(nèi)變化時，項目總工期隨執(zhí)行速率rj的增加而減少，隨執(zhí)行速率rj減少而增加，命題得證。

命題2若工序j為逆控制工序，當(dāng)工序執(zhí)行速率rj在[ri,upj/dj]內(nèi)變化時，減少工序執(zhí)行速率rj，項目總工期減少，增加工序執(zhí)行速率rj，項目總工期增加。

命題3若工序j為開始控制工序，當(dāng)工序執(zhí)行速率rj在[rk,ri]內(nèi)變化時，增加或減少工序執(zhí)行速率rj，項目總工期不變。

命題4若工序j為結(jié)束控制工序，當(dāng)工序執(zhí)行速率rj在[ri,rk]內(nèi)變化時，增加或減少工序執(zhí)行速率rj，項目總工期不變。

命題2、3、4的證明方法同命題1。上述命題闡述了控制工序類型在保持不變的前提下，工序執(zhí)行速率變化與項目總工期之間的關(guān)聯(lián)，項目管理者可根據(jù)其中的規(guī)律更精確地控制重復(fù)性項目總工期。

2.3 問題性質(zhì)

命題1～4建立了控制工序執(zhí)行速率與項目總工期之間的聯(lián)系，由于工序的執(zhí)行速率是由雇傭的工作隊數(shù)量和單元工期決定，因此上述命題本質(zhì)上建立的是工作隊雇傭數(shù)量與項目總工期之間的聯(lián)系。由于截止日期問題的目標(biāo)是求得一個工作隊雇傭數(shù)量最少的進度計劃，利用上述命題可得到最優(yōu)的截止日期問題進度計劃應(yīng)滿足如下幾個條件。

條件2和3的證明方法同條件1。

上述三個條件揭示了截止日期問題的一些規(guī)律，其中，條件1利用了項目總工期公式中逆控制工序具有雇傭工作隊數(shù)量和項目總工期同向變化的特點，即工作隊雇傭數(shù)量減少項目總工期也減少。條件2和條件3則利用了開始控制工序和結(jié)束控制工序工作隊雇傭數(shù)量在一定范圍內(nèi)變化不影響項目總工期的特點。這些性質(zhì)對于實際工程項目的進度安排具有指導(dǎo)意義，項目管理者可以根據(jù)這些性質(zhì)判斷一個調(diào)度方案是否合理。同時，這些性質(zhì)可以進一步為調(diào)度算法的設(shè)計提供依據(jù)。

3 分支限界算法設(shè)計

目前求解截止日期問題的方法主要集中于啟發(fā)式算法。啟發(fā)式算法通常能夠得到一個較優(yōu)的可行解，但重復(fù)性項目往往投資和建設(shè)規(guī)模較大，求得精確的最優(yōu)調(diào)度方案對節(jié)約項目成本和資源具有非常重要的意義。分支限界算法是一種求解問題精確解的有效算法，其算法流程包括分支、限界和剪枝幾個步驟?；谏鲜鼋刂谷掌趩栴}的性質(zhì)，本文設(shè)計了一種具有針對性的分支限界算法實現(xiàn)對截止日期問題的精確求解。

3.1 分支策略

截止日期問題的解空間可由一個樹型結(jié)構(gòu)進行組織，每一層的結(jié)點分別對應(yīng)一個工序的工作隊雇傭數(shù)量情況，如圖4所示。每個結(jié)點包含了相應(yīng)的進度計劃信息，包括工序編號，工序單元工期，工作數(shù)量等。分支限界算法從根結(jié)點出發(fā)，不斷選擇當(dāng)前未分支的結(jié)點中目標(biāo)下界最小的結(jié)點作為拓展結(jié)點進行分支，分支的數(shù)量由工序i的緊后工序j的工作隊雇傭量上限決定。

圖4 解空間圖示

3.2 限界策略

為求得截止日期問題的一個下界，對工序工作隊雇傭數(shù)量這一整數(shù)變量xi進行連續(xù)松弛，并不考慮其資源約束。在該情況下，顯然當(dāng)所有工序的執(zhí)行速率都相同且總工期等于截止日期時，項目所需的工作隊數(shù)量最少，此時工序的執(zhí)行速率可由式(10)確定。

r=(m-1)/(Td-T1)

(10)

每個工序的工作隊理想雇傭數(shù)量可由式(11)計算得到。

ci=diri=(m-1)di/(Td-T1)

(11)

(12)

將式(12)從整體考慮到局部，當(dāng)某個結(jié)點對應(yīng)的前j個工序的工作隊雇傭數(shù)量已確定，則該結(jié)點的目標(biāo)下界估計式如式(13)所示。

(13)

3.3 剪枝策略

剪枝策略是分支限界算法在搜索迭代過程中利用已知的信息判斷結(jié)點是否可行或是否有可能成為最優(yōu)解，若能夠判斷出不可行或不是最優(yōu)解則刪除該結(jié)點以加快算法搜索效率。利用本文提出的截止日期問題性質(zhì)以及問題固有結(jié)構(gòu)，可以設(shè)計出如下三個剪枝策略。

剪枝策略1：若某一節(jié)點的項目總工期估計下界fT超過截止日期Td，即fT>Td，應(yīng)刪除該結(jié)點。項目總工期的估計下界可由式(14)計算。

(14)

3.4 算法流程

基于上述分支策略、限界策略和剪枝策略，本文設(shè)計的針對截止日期問題求解的分支限界算法步驟流程如下所示：

步驟1建立初始結(jié)點并初始化參數(shù)；

步驟2選擇下界最小的結(jié)點作為拓展結(jié)點；

步驟3當(dāng)沒有結(jié)點能夠被選做拓展結(jié)點時，算法結(jié)束，得到最優(yōu)解，否則，轉(zhuǎn)步驟4；

步驟4對當(dāng)前拓展結(jié)點進行分支，并計算子結(jié)點參數(shù)；

步驟5利用剪枝策略刪除不滿足條件結(jié)點；

步驟6標(biāo)記該拓展結(jié)點為已拓展并轉(zhuǎn)步驟2。

4 算例分析

4.1 計算效果分析

本文選用文獻[9]中的案例驗證算法計算效果的有效性。該項目為一高速公路項目，共包含24個工序和10個單元。利用本文提出的分支限界算法對該案例進行求解，并與CPM/LOB[11]，ALISS[13]和SHLOB[9]三種啟發(fā)式算法的計算結(jié)果進行比較，其結(jié)果如表1所示。

表1 案例計算結(jié)果

由表1可知，相對于現(xiàn)有算法，本文提出的分支限界算法能夠得到一個最優(yōu)的調(diào)度方案。CPM/LOB方法雖然都能夠得到一個工作隊雇傭數(shù)量較少的調(diào)度方法，但是無法滿足截止日期約束，是不可行的。ALISS能夠生成一個滿足截止日期的方案，但是需要雇傭更多的工作隊，項目成本較高。SHLOB方法也得到了問題的最優(yōu)解，但是該方法實際上引入了隨機搜索機制，計算效果并不穩(wěn)定。通過數(shù)值實驗，使用SHLOB算法求解該案例1000次，僅5次能夠得到最優(yōu)解，計算效果并不十分理想。

4.2 計算效率分析

進一步分析本文提出的剪枝策略對算法計算效率的影響。依據(jù)剪枝策略的選擇，考慮3個版本的分支限界算法。其中，算法1僅使用剪枝策略1，算法2使用剪枝策略1和2，算法3則使用所有剪枝策略。測試算例根據(jù)表2的參數(shù)設(shè)置隨機生成。

表2 算例參數(shù)設(shè)置

本文采用Microsoft Visual C++實現(xiàn)算法程序，代碼在一個主頻為2.4GHz、內(nèi)存為4G的個人計算機上運行。測試完所有案例后，采用如下3個指標(biāo)衡量算法的計算效率：

(1)ACT：算法平均計算時間。

(2)MCT：算法最大計算時間。

(3)NUM：算法遍歷的結(jié)點數(shù)量。

3個版本算法的計算結(jié)果如表3～5所示。從表中可以看出，所有算法的計算時間都隨著案例規(guī)模的增加而增加。所有算法中，算法3無論是計算時長還是計算時間增長速度都顯著優(yōu)于算法1和算法2，即使用所有剪枝函數(shù)能夠最大限度提高算法的計算效率。對比直接求解截止日期問題數(shù)學(xué)模型的計算效率，表6給出了采用Lingo優(yōu)化求解器求解相同規(guī)模案例的計算時間，可見本文提出的分支限界算法計算效率顯著優(yōu)于Lingo求解器。

從遍歷結(jié)點數(shù)量看，采用不同的剪枝策略會導(dǎo)致不同的遍歷結(jié)果。以工序數(shù)量為30時為例，相對于算法1，算法2能夠少遍歷36.6%的結(jié)點，而相對于算法2，算法3則能夠少遍歷96.5%的結(jié)點?？梢姡糁瘮?shù)能夠有效的識別非最優(yōu)解從而加快算法的搜索速率，但是不同的剪枝策略對算法搜索效率的提高程度有所不同。其中，剪枝策略3，即利用逆控制工序和結(jié)束控制工序性質(zhì)的剪枝策略，對計算效率的提升最為顯著。

表3 算法1計算效率

表4 算法2計算效率

表5 算法3計算效率

表6 Lingo計算效率

5 結(jié)論

本文從控制工序性質(zhì)出發(fā)，對重復(fù)性項目截止日期問題進行分析。在確定不同類型控制工序穩(wěn)定區(qū)間的基礎(chǔ)上，將重復(fù)性項目總工期公式轉(zhuǎn)換為基于執(zhí)行速率的動態(tài)形式，建立工序執(zhí)行速率與項目總工期的關(guān)系，并推得最優(yōu)截止日期問題進度方案所需要滿足的條件。項目管理人員可以利用這些性質(zhì)檢驗一個調(diào)度方案是否可行且經(jīng)濟。進一步地，本文設(shè)計了一個具有針對性的分支限界算法，利用所提出的截止日期問題性質(zhì)設(shè)計剪枝函數(shù)并整合到算法流程中。算例的計算結(jié)果表明本文提出的算法能夠得到問題的精確最優(yōu)解，且計算效率優(yōu)于啟發(fā)式算法以及模型求解器。

本文研究主要針對的是重復(fù)性項目截止日期問題，而對于其他類型的調(diào)度優(yōu)化問題也可能存在類似的性質(zhì)和特點，如費用優(yōu)化問題和時間費用權(quán)衡問題等。因此，基于控制工序性質(zhì)分析其他重復(fù)性項目調(diào)度優(yōu)化問題的規(guī)律特征，并以此設(shè)計更有效的調(diào)度優(yōu)化算法是未來非常具有潛力的研究方向。