熊 俊， 孫 聰， 劉 青， 馬博翔,3， 張立輝

(1. 國網(wǎng)北京市電力公司， 北京 100041； 2. 華北電力大學(xué) a. 經(jīng)濟(jì)與管理學(xué)院； b. 新能源電力與低碳發(fā)展研究北京市重點(diǎn)實(shí)驗(yàn)室， 北京 102206； 3. 清華大學(xué) 電氣學(xué)院， 北京 100084)

當(dāng)前我國處于基本建設(shè)大發(fā)展時(shí)期，大量的重復(fù)性建設(shè)項(xiàng)目如隧道工程、地鐵等正在興建或規(guī)劃之中，這些項(xiàng)目投資大、工期長，因此對它們的研究具有很實(shí)際的意義。重復(fù)性建設(shè)項(xiàng)目是指在建設(shè)工程的每個(gè)單元各個(gè)工序不斷重復(fù)進(jìn)行的項(xiàng)目[1]。由于工作連續(xù)性和資源恒定性是重復(fù)性建設(shè)項(xiàng)目調(diào)度計(jì)劃中需重點(diǎn)考慮的因素。因此，近年來，國內(nèi)外學(xué)者對兩者進(jìn)行了大量的研究，例如Vanhoucke[2]提出工作連續(xù)性約束能使每個(gè)工序的施工空閑時(shí)間最小化，這在一定程度上能縮短工期；而Birrell[3]提出維持工作連續(xù)性將導(dǎo)致工期變長； Selinger[4]也認(rèn)為不保持工作連續(xù)性將有可能進(jìn)一步縮短項(xiàng)目工期。Zhang等[5,6]提出資源恒定性約束有利于高效利用資源，但同時(shí)也可能造成工期的延長，其還研究了資源連續(xù)性的相關(guān)原理。因此，有必要權(quán)衡工作連續(xù)性與資源恒定性對離散時(shí)間費(fèi)用權(quán)衡(Discrete Time-Cost Trade-off Problem，DTCTP)的影響，但目前相關(guān)研究較少。DTCTP是項(xiàng)目調(diào)度中的一種雙目標(biāo)優(yōu)化問題，屬于強(qiáng)NP - 難問題[7]。DTCTP的解決方法主要有基于動(dòng)態(tài)規(guī)劃[8]和分支定界的精確算法[9]，也有基于啟發(fā)式規(guī)則的各種啟發(fā)式算法[10]以及智能算法[7,11]。目前對該問題的研究大都采用智能算法求解，如Hyari等[12]構(gòu)建了能權(quán)衡總工期與總費(fèi)用的遺傳算法，并采用Pareto最優(yōu)性原理對重復(fù)性建設(shè)項(xiàng)目的調(diào)度方案優(yōu)化；Zhang等[1]用遺傳算法解決了軟邏輯下重復(fù)性項(xiàng)目的時(shí)間費(fèi)用權(quán)衡問題；Long等[11]設(shè)計(jì)了考慮工序優(yōu)先關(guān)系和工作連續(xù)性的遺傳算法，并將其應(yīng)用于優(yōu)化重復(fù)性項(xiàng)目的工期和費(fèi)用。但是，針對工作連續(xù)性和資源恒定性的算法還有待進(jìn)一步研究。所以，本文作者通過探索項(xiàng)目施工過程中工作、資源與時(shí)間費(fèi)用問題的內(nèi)在關(guān)系，構(gòu)建隧道建設(shè)中關(guān)于工作可間斷和資源可波動(dòng)的離散時(shí)間費(fèi)用權(quán)衡模型(DTCTP-wr)，提出一種雙鏈?zhǔn)秸麛?shù)編碼和隨機(jī)單點(diǎn)交叉算子的改進(jìn)算法，并以一個(gè)實(shí)際的電力隧道建設(shè)項(xiàng)目為例，驗(yàn)證算法的有效性和合理性，并得出工作連續(xù)性約束和資源恒定性約束對項(xiàng)目造成的影響。而且，該算法也能移植到其他重復(fù)性項(xiàng)目的調(diào)度中，為我國基礎(chǔ)設(shè)施建設(shè)提供更為科學(xué)、經(jīng)濟(jì)的調(diào)度方案。

1 DTCTP-wr

1.1 問題描述

重復(fù)性項(xiàng)目問題描述如下：設(shè)有N個(gè)工序，每個(gè)工序有M個(gè)相同的單元(例如，隧道具有多個(gè)相似的豎井)。工序1是開始工序，工序N是結(jié)束工序。工序i(i=1,…,N)的施工情況與它的緊前工序有關(guān)，需與緊前工序滿足結(jié)束 - 開始的時(shí)間約束。工序i的第j單元表示為子工序aij，并且有Ki種執(zhí)行模式。aij的工期用dijk,k=1,2,…,Ki表示，變量k表示執(zhí)行模式選擇。

項(xiàng)目的總費(fèi)用由以下部分組成：直接費(fèi)用DC，間接費(fèi)用IC和所有工序的資源閑置費(fèi)用IRC。各部分費(fèi)用具體計(jì)算如下：

采用式(1)計(jì)算項(xiàng)目直接費(fèi)用DC，由項(xiàng)目中每個(gè)工序各單元的材料費(fèi)用MC、勞動(dòng)力費(fèi)用WC、設(shè)備費(fèi)用EC之和構(gòu)成。

DC=MC+WC+EC

(1)

采用式(2)計(jì)算項(xiàng)目間接費(fèi)用IC，由項(xiàng)目中每天對應(yīng)的費(fèi)用之和構(gòu)成。

(2)

式中：ICRd為第d天的間接費(fèi)用；D為項(xiàng)目的總工期。

采用式(3)計(jì)算資源閑置費(fèi)用IRCi。資源閑置費(fèi)用是由于承包商執(zhí)行模式選擇不當(dāng)，造成資源閑置所產(chǎn)生的費(fèi)用。若工序i須保證資源恒定性約束，IRCi等于所選擇執(zhí)行模式的勞動(dòng)費(fèi)用率(包括人、料、機(jī)的閑置費(fèi))與中斷天數(shù)的積。否則，若工序i無資源恒定性約束，IRCi等于所有可選執(zhí)行模式中勞動(dòng)費(fèi)用率最高值與中斷天數(shù)的積。

(3)

式中：xijk為二進(jìn)制數(shù)(如果子工序aij在模式k下執(zhí)行，xijk取1；否則，xijk取0)；INTi為工序i的中斷天數(shù)；Ri為工序i資源恒定性約束；集合Θ表示所有工序的資源恒定約束關(guān)系。

1.2 數(shù)學(xué)模型

目標(biāo)函數(shù)：

MCij+IRCi]+IC

(4)

約束條件：

sij+dij≤spj,p∈(j,N],i=1,2,…,N;j=1,2,…,M

(5)

(6)

(7)

(8)

(9)

xijk-xi(j+1)k=0,i∈Θ;j=1,2,…,M-1;k=1,2,…,Ki

(10)

(11)

Ft≤Tmax

(12)

式中：i為工序數(shù)；j為單元數(shù)；N為工序總數(shù)；M為單元總數(shù)。目標(biāo)函數(shù)式(4)最小化項(xiàng)目總成本。約束條件式(5)表示在同一工序中子工序aij完成后子工序ai(j+1)才可能開始，sij為子工序aij的開始時(shí)間。約束條件式(6)中dij指工序i單元j的持續(xù)時(shí)長。約束條件式(7)中yijl指工序i單元j選擇第l種模式時(shí)yijl=1。約束條件式(6)(7)要求每一工序需滿足給定的邏輯施工順序，即子工序ai(l+1)只能在子工序ail結(jié)束后才能開始(如果子工序ai(l+1)滿足條件，yijl取1；否則，yijl取0)。約束(8)表示每個(gè)子工序只能有一種邏輯調(diào)度順序。約束(9)表明為了滿足工作連續(xù)性約束，中斷時(shí)間必須為0，集合Φ表示所有工序的工作連續(xù)性約束關(guān)系。約束條件式(10)要求所有滿足資源恒定約束的工序均需執(zhí)行同樣的執(zhí)行模式。約束條件式(11)表示任一子工序僅有一種施工順序，同一工序內(nèi)的任何兩個(gè)子工序不能同時(shí)施工。約束條件式(12)要求項(xiàng)目的工期Ft不能超過給定的最大工期限制Tmax。

2 改進(jìn)遺傳算法

由于DTCTP問題的計(jì)算規(guī)模相當(dāng)大[7]，非線性方法很難在短時(shí)間內(nèi)得到令人滿意的結(jié)果。因此，針對所研究的問題，本文設(shè)計(jì)了相應(yīng)的雙鏈染色體編碼方式、帶懲罰函數(shù)的適應(yīng)度值計(jì)算法，以及單點(diǎn)交叉算子和變異算子，并最終提出了一種具有求解能力的改進(jìn)遺傳算法。

2.1 雙鏈染色體編碼

圖1 染色體結(jié)構(gòu)

2.2 適應(yīng)值計(jì)算

對于DTCTP-wr，在調(diào)度方案集中有可能存在一些總工期超期或總費(fèi)用超額的方案。所以本文提出了一種懲罰機(jī)制，確保這些方案比在工期范圍內(nèi)的項(xiàng)目適應(yīng)度值小。對于個(gè)體I,Ft(I)為個(gè)體I對應(yīng)的最小總工期。修正其最小總工期目標(biāo)函數(shù)為：

F′c(I)=(1+βt)Fc(I)

(14)

式中：βt為一個(gè)正懲罰因子，按式(15)計(jì)算。

(15)

因?yàn)镈TCTP-wr屬于最小化雙目標(biāo)問題，所以適應(yīng)度函數(shù)應(yīng)轉(zhuǎn)化為：

fc(I)=max{F′c(1)，F(xiàn)′c(2),…,F′c(P)}-F′c(I)

(16)

式中：P為種群規(guī)模。

適應(yīng)度值確定后，接下來就選擇當(dāng)前代的最優(yōu)個(gè)體進(jìn)行迭代遺傳操作。

2.3 單點(diǎn)交叉算子

對執(zhí)行模式鏈進(jìn)行單點(diǎn)交叉操作。令隨機(jī)整數(shù)r(0≤r≤N)作為單點(diǎn)交叉起點(diǎn)。工序i=1,2,…,r所在的染色體，從一個(gè)父代中得到染色體片段，即

(17)

工序i(r

(18)

與執(zhí)行模式的單點(diǎn)交叉操作方法類似，邏輯順序鏈也用同樣的方法，但須注意的是單點(diǎn)交叉點(diǎn)的位置需要重新隨機(jī)生成。

2.4 變異算子

對于執(zhí)行模式鏈，隨機(jī)選取工序t，t∈[1,N]作為突變點(diǎn)。若工序t有資源恒定性約束，那么，工序t所在的染色體片段需在隨機(jī)整數(shù)[1,Kt]取值。否則，保證工序t中有且僅有一個(gè)單元在[1,Kt]隨機(jī)取值即可。

對于邏輯順序鏈，首先選出變異的工序t，即隨機(jī)生成整數(shù)t，t∈[1,N]；然后，選出工序t所在的變異單元，即生成兩個(gè)隨機(jī)整數(shù)u,v,u,v∈[1,M]；最后，將工序t的第u單元的染色體信息與第v單元的染色體片段信息交換。

2.5 調(diào)度算法

為了將每個(gè)染色體中的信息整合為與工期相關(guān)的信息，進(jìn)而求得其對應(yīng)的總工期和總費(fèi)用。對于給定個(gè)體I，調(diào)度算法具體步驟如下。

步驟1：初始化種群P，種群大小為Np，設(shè)當(dāng)前遺傳代數(shù)gen為1 ；

步驟2：通過模型中的約束條件解析執(zhí)行模式鏈和邏輯順序鏈，計(jì)算子工序aij的工期dij并根據(jù)模型中的約束條件得到當(dāng)前代的最小總費(fèi)用。根據(jù)所要求解的子問題計(jì)算所有個(gè)體的適應(yīng)度值，然后對種群進(jìn)行輪盤賭選擇，生成子種群C；

步驟3：對子種群C中的所有個(gè)體進(jìn)行交叉算子，生成新的子種群C1；

步驟4：對子種群C1中所有個(gè)體執(zhí)行變異算子，生成新的子種群C2；

步驟5：分別從種群P和子種群C2中各挑選適應(yīng)度較高的1/2個(gè)體進(jìn)行合并得到新的種群P；

步驟6：令gen=gen+1，若gen的值小于設(shè)定的最大遺傳代數(shù)，返回步驟2；否則跳出程序并輸出近似最優(yōu)解。

3 結(jié)果及分析

本文采用一個(gè)明開電力隧道建設(shè)項(xiàng)目作為算例[13]。該項(xiàng)目由五個(gè)工序構(gòu)成，分別是挖隧道，填地基，做豎井，上蓋板和鋪頂面。項(xiàng)目管理費(fèi)用為2500美元/d。項(xiàng)目其他基本信息如表1所示。dijk可通過dijk=Qij/Pik得到。下面將通過四種情形進(jìn)行討論：

情形1: 所有工序沒有工作連續(xù)性約束，但均有資源恒定性約束；

情形2: 所有工序都有工作連續(xù)性約束和資源恒定性約束；

情形3: 所有工序均有工作連續(xù)性約束，但沒有資源恒定性約束；

情形4: 所有工序沒有工作連續(xù)性約束，同時(shí)也沒有資源恒定性約束。

表1 項(xiàng)目基本數(shù)據(jù)

3.1 工作可間斷影響分析

圖2 有/無工作連續(xù)性約束下時(shí)間 - 費(fèi)用曲線

圖2為有/無工作連續(xù)性約束下時(shí)間 - 費(fèi)用曲線，通過比較情形1和情形2的結(jié)果可知，在資源恒定性約束情況下，工作可間斷對項(xiàng)目成本和時(shí)間的影響。(1)如圖2所示，總工期范圍在106～118 d內(nèi)，情形1，2的時(shí)間 - 費(fèi)用權(quán)衡曲線基本上是重合的。這是由于在該隧道建設(shè)項(xiàng)目中，只有當(dāng)所有工序都沒有中斷或存在很少中斷的情況下才會(huì)出現(xiàn)項(xiàng)目工期較長的情況。(2)如圖2所示，情形1得到的方案數(shù)明顯比情形2多， 這是因?yàn)椴豢紤]工作連續(xù)性，子工序與子工序之間的時(shí)間關(guān)系將更加靈活，約束時(shí)間不再必須取0。(3)表2，3分別為情形1，2下時(shí)間 - 費(fèi)用曲線的詳細(xì)計(jì)算結(jié)果。據(jù)表2，3可知，兩種情形下主要的區(qū)別在于方案中的最小項(xiàng)目總工期。表3列出了情形2下詳細(xì)的計(jì)算結(jié)果，其中最小項(xiàng)目總工期為104.82 d，對應(yīng)的總費(fèi)用為1654977美元。如果所有工序允許工作不連續(xù)(情形1)，最小項(xiàng)目總工期將縮短為94 d，相比節(jié)約了10.32%；但是對應(yīng)的費(fèi)用相應(yīng)也提高到了1758235美元。情形3，4也有相似的結(jié)論，具體結(jié)果分別見表4，5。可見，允許工作中斷將有利于項(xiàng)目縮短總工期。

3.2 資源可波動(dòng)影響分析

圖3為有/無資源恒定性約束下時(shí)間 - 費(fèi)用曲線,通過情形1和情形4的結(jié)果比較可知，在沒有工作連續(xù)性的情況下，資源可波動(dòng)對項(xiàng)目成本和時(shí)間的影響。(1)如圖3所示，在最大工期限制范圍內(nèi)，每個(gè)可行的項(xiàng)目方案，情形4中的總費(fèi)用總是低于情形1。這種現(xiàn)象可解釋為：當(dāng)工序不需維持資源恒定性約束時(shí)，該工序中所有的子工序都不會(huì)對項(xiàng)目工期造成影響，并且將會(huì)選擇最經(jīng)濟(jì)的執(zhí)行模式。但是，當(dāng)所有工序有資源恒定約束，子工序需要根據(jù)其他相關(guān)子工序執(zhí)行模式選擇情況來選擇類似的執(zhí)行模式，而對其他子工序經(jīng)濟(jì)的執(zhí)行模式并不一定適用于該子工序。(2)根據(jù)圖3，結(jié)合對比表2，5中的項(xiàng)目總費(fèi)用可知，當(dāng)截止日期為Tmax=94 d時(shí)，這兩種情形下的項(xiàng)目總費(fèi)用差值達(dá)到最大值(1758235-1723960)=34275美元。因?yàn)榭偣て谠蕉?，中斷天?shù)越少，不考慮資源恒定性的情形4下，對應(yīng)的資源閑置費(fèi)用就越低，而情形1中資源閑置費(fèi)用也會(huì)降低，根據(jù)公式(3)可知，中斷天數(shù)的變化在這一階段對資源閑置費(fèi)用起主要的影響；(3)據(jù)表2，5可知，當(dāng)所有工序沒有資源恒定性約束時(shí)的最小項(xiàng)目總費(fèi)用1615909美元，而滿足資源恒定性約束時(shí)最小總費(fèi)用為1618868美元，兩者基本相等。而對應(yīng)的總工期前者僅113 d遠(yuǎn)少于后者的118 d。情形2，3也有相似的結(jié)論，具體的結(jié)果分別見表3，4?？梢?，取消資源恒定性約束將有利于項(xiàng)目減少總費(fèi)用。

3.3 雙重因素組合影響分析

通過情形2和情形4的結(jié)果比較可知，工作可間斷和資源可波動(dòng)雙重因素影響下對項(xiàng)目成本和時(shí)間的影響。(1)據(jù)表3和表5可知，情形2的可選擇方案數(shù)明顯少于情形4。主要原因有兩點(diǎn)，一是因?yàn)榍樾?考慮工作連續(xù)性后，子工序與子工序之間的時(shí)間約束比情形4強(qiáng)，因而導(dǎo)致情形2中部分方案丟失，二是因?yàn)橘Y源恒定性要求，子工序之間必須選擇同一執(zhí)行模式，這樣也大大減少了可選的方案。(2)對比觀察表3，5可知，當(dāng)選擇總費(fèi)用相差不大的方案時(shí)，在表3選擇總費(fèi)用為1619612美元的方案，對應(yīng)表5與之最接近的總費(fèi)用為1619954美元的方案，前者的工期比后者長(118.48-108.41)=10 d。當(dāng)選擇總工期相差不大的方案時(shí)，在表3選擇總工期為104.82 d的方案，對應(yīng)表5與之接近的總工期為104.89 d的方案，前者的總費(fèi)用比后者高(1654977-1622063)=32914美元。因此，對于工作連續(xù)性和資源連續(xù)性的選擇，項(xiàng)目管理者應(yīng)根據(jù)具體的項(xiàng)目目標(biāo)制定與之契合的方案。

表3 情形2下時(shí)間 - 費(fèi)用曲線的詳細(xì)計(jì)算結(jié)果

圖3 有/無資源恒定性約束下時(shí)間 - 費(fèi)用曲線

表4 情形3下時(shí)間 - 費(fèi)用曲線的詳細(xì)計(jì)算結(jié)果

表5 情形4下時(shí)間 - 費(fèi)用曲線的詳細(xì)計(jì)算結(jié)果

4 結(jié) 論

(1)構(gòu)建了工作可間斷和資源可波動(dòng)的離散時(shí)間費(fèi)用權(quán)衡優(yōu)化模型(DTCTP-wr)，并通過一個(gè)實(shí)際的電力隧道工程建設(shè)項(xiàng)目驗(yàn)證了其可用性和合理性。

(2)結(jié)合研究的問題，提出了基于雙鏈?zhǔn)秸麛?shù)編碼和隨機(jī)單點(diǎn)交叉算子的改進(jìn)遺傳算法。該算法在確保近似最優(yōu)解的條件下有效地減少了運(yùn)算量，并且只要稍加擴(kuò)展與完善就可用于國家基礎(chǔ)建設(shè)項(xiàng)目的規(guī)劃中。

(3)定量驗(yàn)證了允許工作間斷有利于項(xiàng)目縮短總工期；允許資源波動(dòng)有利于減少項(xiàng)目總費(fèi)用。在考慮工作可間斷和資源可波動(dòng)雙因素的影響下，管理者可根據(jù)項(xiàng)目的具體要求有針對性地得到最佳的項(xiàng)目調(diào)度方案。