劉 堯,宋元斌,李云祥

(上海交通大學(xué) 船舶海洋與建筑工程學(xué)院,上海 200240)

0 概述

隨著工程項目規(guī)模的不斷擴大,解決施工進度計劃的快速編制問題變得越發(fā)重要。施工進度計劃的快速編制主要包括兩項關(guān)鍵技術(shù),即施工順序的表述模型和與之對應(yīng)的求解算法。施工順序知識用于推導(dǎo)進度計劃編制中施工活動的先后順序,為工程模型到數(shù)學(xué)模型的轉(zhuǎn)換提供依據(jù);調(diào)度模型的求解是一種典型的NP難問題,根據(jù)不同的調(diào)度模型有不同的求解方法。

復(fù)雜施工排序方案中的表述問題主要分為兩類。第一類為施工活動的時間順序表述問題,主要用于推理進度計劃中的施工活動先后順序。文獻[1]用時間區(qū)間描述活動的持續(xù)狀態(tài),并定義了2個時間區(qū)間之間的13種關(guān)系。后續(xù)研究者在其基礎(chǔ)上擴展引入了最大時間間隔[2]、負時間間隔[3]和時間約束柔性[4]等概念,解決了施工活動順序表達上的大部分難題。第二類為施工計劃中的邏輯關(guān)系表述問題,即施工活動與時間關(guān)系間的邏輯關(guān)系,許多學(xué)者對其進行了研究。文獻[5]使用Disjoint描述2個時間關(guān)系之間存在“Or”邏輯關(guān)系。文獻[6]用包含(→)、等價(?)和異或(?)3個邏輯運算符來描述邏輯關(guān)系。文獻[7]提出活動之間的互斥和共存關(guān)系,用以描述備擇施工方案之間的關(guān)系。

研究者在調(diào)度模型的算法設(shè)計中,會依據(jù)時間約束[8]、資源約束[9]等條件改進算法,也會直接使用調(diào)度工具[10]進行求解。文獻[11]在電網(wǎng)規(guī)劃上使用布爾變量來簡單表示區(qū)域電網(wǎng)投運與否的狀態(tài),從而計算電網(wǎng)的最小成本。文獻[12]將傳統(tǒng)遺傳算法與模擬退火算法相結(jié)合來解決Web服務(wù)組合質(zhì)量優(yōu)化問題。文獻[13]用改進的遺傳算法對BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)重進行賦值,用以加快神經(jīng)網(wǎng)絡(luò)的收斂速率。上述規(guī)劃模型采用互相獨立的布爾變量表示簡單邏輯關(guān)系進行遺傳算法的改進設(shè)計,均未解決復(fù)雜邏輯關(guān)系的計算難題。

求解調(diào)度模型主要分為精確式算法和啟發(fā)式算法。精確式算法受線性規(guī)劃求解器容許決策變量數(shù)目的限制,在求解中小規(guī)模的調(diào)度問題時具有速度快、結(jié)果精確的優(yōu)點,但在求解帶有大量邏輯關(guān)系的超大型復(fù)雜調(diào)度模型時,卻表現(xiàn)出時間效率低下的問題,不能滿足一些規(guī)模龐大的優(yōu)化調(diào)度問題求解需求。啟發(fā)式算法主要用于快速有效地求解大規(guī)模問題的較優(yōu)解。因此,采用啟發(fā)式算法求解帶有較多邏輯關(guān)系的復(fù)雜調(diào)度問題是合理的選擇。

遺傳算法是一種經(jīng)典的啟發(fā)式算法,被廣泛應(yīng)用于工程計劃,如施工項目[14]、流水作業(yè)[15]、高速公路建設(shè)[16]等。為了滿足特定領(lǐng)域的需求,研究者也會對遺傳算法進行相應(yīng)改進。文獻[17]通過改進交叉算子,解決了含有多個目標(biāo)的最優(yōu)化模型求解問題。文獻[18]在處理裝配式建筑構(gòu)件運輸問題上,加入運輸節(jié)點的權(quán)重計算,加快種群的收斂速度。由于上述算法沒有考慮工程模型中的備擇和依存關(guān)系,因此難以描述復(fù)雜調(diào)度模型中的邏輯關(guān)系。

本文基于文獻[6]的邏輯運算符,增加了邏輯符XOR、XNOR和IF-THEN來表示活動之間和時間關(guān)系之間的邏輯關(guān)系,編程實現(xiàn)復(fù)雜調(diào)度模型到混合整數(shù)規(guī)劃模型[19]的自動轉(zhuǎn)換,并提出一種解決該問題的改進遺傳算法,采取基于工程邏輯關(guān)系布爾變量劃分的順序編碼方式,將染色體劃分為獨立變量和半獨立變量編碼基因段,從而解決帶有大量依賴邏輯關(guān)系的調(diào)度模型求解問題。

1 調(diào)度模型中邏輯關(guān)系的表述

本節(jié)在探究時間關(guān)系之間的互斥(XOR)與共存(XNOR)邏輯關(guān)系基礎(chǔ)上,提出用“IF-THEN”表示活動或時間關(guān)系之間存在的依賴邏輯關(guān)系,同時探究將其轉(zhuǎn)化進入混合整數(shù)線性規(guī)劃的數(shù)學(xué)理論方法。文中符號說明如表1所示。

表1 符號定義說明

為說明包含時間關(guān)系的邏輯關(guān)系,本文引入布爾決策變量ER(i,j)用以描述時間關(guān)系之間的邏輯關(guān)系,下標(biāo)中R表示該變量為時間關(guān)系的布爾變量,(i,j)表示此為描述活動i和活動j的時間關(guān)系。如果一個時間關(guān)系R(i,j)被選擇執(zhí)行,則對應(yīng)的決策變量ER(i,j)被賦值為1,否則賦值為0。

(1)

邏輯關(guān)系的線性約束表達如表2所示。

表2 邏輯關(guān)系與線性約束的關(guān)系

Table 2 Relationship between logical relations and linear constraints

邏輯關(guān)系線性約束活動i與j為互斥關(guān)系Ei + Ej = 1活動i與j為共存關(guān)系Ei = Ej活動i與j為依賴關(guān)系Ei ≤ Ej活動i與時間關(guān)系R(j,k)為互斥關(guān)系Ei + ER(j,k) = 1活動i與時間關(guān)系R(j,k)為共存關(guān)系Ei = ER(j,k)活動i與時間關(guān)系R(j,k)為依賴關(guān)系Ei ≤ ER(j,k)時間關(guān)系R(i,j)與R(k,l)為互斥關(guān)系ER(i,j) + ER(k,l) = 1時間關(guān)系R(i,j)與R(k,l)為共存關(guān)系ER(i,j) = ER(k,l)時間關(guān)系R(i,j)與R(k,l)為依賴關(guān)系ER(i,j) ≤ ER(k,l)

2 復(fù)雜調(diào)度模型的建立與求解

為克服精確式算法求解帶有大量邏輯關(guān)系的超大型工程存在的不足,本文設(shè)計了基于布爾變量劃分的順序編碼方式,在遺傳算法中對違反約束規(guī)則的個體進行了修正。

2.1 調(diào)度模型

施工調(diào)度計劃最主要的任務(wù)之一是確定最短工期下的施工排序方案。本文的調(diào)度模型優(yōu)化目標(biāo)使項目結(jié)束時間FP最小。計算工期的混合整數(shù)線性規(guī)劃模型如下:

目標(biāo)函數(shù)如式(2)所示。

MinZ=FP

(2)

約束條件如式(3)～式(17)所示。

a′×Si-a′×Sj+Di+L(i,j)≤0

?R(i,j),1≤i≤n,1≤j≤n

(3)

a′×Si-a′×Sj+EAi×Di+L(i,j)≤0

?R(i,j),1≤i≤n,1≤j≤n

(4)

a′×Si-a′×Sj+Di+L(i,j)-M(1-ER(i,j))≤0

?R(i,j),1≤i≤n,1≤j≤n

(5)

a′×Si-a′×Sj+EiA×Di+L(i,j)-

M(1-ER(i,j))≤0,?R(i,j),1≤i,j≤n

(6)

Si≥0,i=1,2,…,n

(7)

Si+Di≤Fp,i=1,2,…,n

(8)

Ei+Ej=1,iXORj

?i,j,1≤i≤n,1≤j≤n

(9)

Ei=Ej,iXNORj,?i,j,1≤i≤n,1≤j≤n

(10)

ER(i,j)+ER(k,l)=1,R(i,j) XORR(k,l)

?R(i,j),R(k,l),1≤i,j,k,l≤n

(11)

ER(i,j)=ER(k,l),R(i,j) XNORR(k,l)

?R(i,j),R(k,l),1≤i,j,k,l≤n

(12)

Ei≤Ej,IFiTHENj

?i,j,1≤i≤n,1≤j≤n

(13)

Ei≤ER(k,l),IFiTHENR(k,l)

?i,1≤i≤n,1≤k,l≤n

(14)

ER(k,l)≤Ej,IFR(k,l) THENj

?i,1≤k,l≤n,1≤j≤n

(15)

ER(i,j)≤ER(k,l),IFR(i,j) THENR(k,l)

?i,j,1≤i,j,k,l≤n

(16)

Ei,Ej,ER(i,j),ER(k,l)∈{0,1}

(17)

目標(biāo)函數(shù)是項目工期的最小化,式(3)是2個確定執(zhí)行的活動之間的時間關(guān)系約束的一般形式,式(4)～式(6)是活動時間關(guān)系的邏輯表示,式(7)限定了所有活動的開始時間均大于等于0,式(8)則限定所有活動必須在工期之內(nèi)完成,式(9)～式(16)是2個備擇活動或備擇時間關(guān)系之間的邏輯關(guān)系表達式,式(17)定義各決策變量為布爾變量。

2.2 遺傳算法求解

基于布爾變量劃分的順序編碼方式,本節(jié)提出一種遺傳算法,將染色體分為獨立變量和半獨立變量編碼基因段,以原調(diào)度模型中的最短工期的倒數(shù)為適應(yīng)度函數(shù),進行最優(yōu)解的搜索,編程實現(xiàn)帶有較多邏輯關(guān)系調(diào)度模型的啟發(fā)式求解。該算法借鑒動態(tài)規(guī)劃的思想[20-22],采用單點交叉與變異,存儲了父代種群運算結(jié)果,將新生成的子代與父代進行比對,相同編碼即可采用同樣的適應(yīng)度運算結(jié)果,有效提高了遺傳算法的運算效率。在遺傳操作后進行沖突檢測,消除由于種群初始化、交叉和變異操作生成的違反約束規(guī)則的個體。

2.2.1 布爾變量的順序編碼

在解決傳統(tǒng)調(diào)度優(yōu)化問題的大多數(shù)遺傳算法中,染色體編碼中的各個基因相互獨立,迭代過程中各基因取值不受其他基因取值的影響,但式(13)～式(16)表明決策變量Ei及ER(i,j)之間存在依賴關(guān)系。為描述該依賴關(guān)系,本文在基因鏈編碼設(shè)計中加入半獨立變量。

在本文模型中所有布爾變量共分為3類:獨立變量,半獨立變量和派生變量。獨立變量指在眾多變量中不受其他變量取值影響的變量,半獨立變量指在其他變量確定后仍有一定取值范圍的變量,派生變量指在獨立變量和半獨立變量確定后取值就確定的變量。

本文算法采用基于布爾變量劃分的順序編碼方式,將整個編碼區(qū)域分為獨立變量區(qū)域(I區(qū))和半獨立變量區(qū)域(II區(qū))。

1)布爾變量編碼規(guī)則

在遺傳算法的改進過程中,為了保證后續(xù)進行遺傳編碼的沖突檢測和修正,確保新產(chǎn)生的染色體的有效性,設(shè)計編碼規(guī)則如下:

(1)在約束中被運算的次數(shù)多的布爾變量優(yōu)先編碼并賦值。

(2)在運算次數(shù)相同的條件下,模型中原始序號靠前的布爾變量優(yōu)先編碼并賦值。

(3)等式約束條件分別對應(yīng)一對獨立變量與派生變量,不等式中對應(yīng)的約束條件Ei≤Ej中,Ei優(yōu)先考慮是否為獨立變量。

假定模型中有n個獨立變量(Ii表示第i個獨立變量),m個半獨立變量(Sj表示第j個半獨立變量),基于布爾變量劃分的順序編碼方式將染色體編碼基因鏈分成I區(qū)編碼區(qū)和II區(qū)編碼區(qū),如圖1所示。

圖1 染色體編碼基因鏈

在包含n個變量的等式或不等式中,總會存在一個獨立變量和派生變量,其余變量為半獨立變量。

在該編碼原則下,II區(qū)編碼基因改變對其他基因位的影響程度將呈降序排列,后續(xù)沖突檢測中對II區(qū)編碼自前向后依據(jù)約束規(guī)則進行修改,這樣可以確保修改后的染色體仍然是有效的個體,同時也可保證對染色體編碼影響最大的編碼改動最小,盡量保持原編碼的有效性。該編碼以線性時間檢測修改染色體,相對于算法適應(yīng)度線性規(guī)劃求解部分的速度影響可以忽略不計。

2)編碼規(guī)則示例

為形象化展示本文算法染色體順序編碼規(guī)則,本節(jié)以一個項目調(diào)度算例來說明,圖2為該工程算例調(diào)度網(wǎng)絡(luò)。

圖2 包含時間關(guān)系和邏輯關(guān)系的工程算例

本算例包含互斥、共存和依賴邏輯關(guān)系,式(18)～式(20)表示3個互斥邏輯關(guān)系,式(21)～式(23)表示3個共存邏輯關(guān)系,式(24)表示一個依賴邏輯關(guān)系。

E2+E5=1

(18)

ER(2,3)+ER(3,2)=1

(19)

ER(3,4)+ER(4,3)=1

(20)

ER(2,3)=ER(3,4)

(21)

ER(3,2)=ER(4,3)

(22)

E5=E6

(23)

E6≤E7

(24)

為了求出最少個數(shù)的獨立變量,設(shè)目標(biāo)函數(shù)為:

?i,R(j,k),1≤i,j,k≤n

(25)

計算求出一組符合本文算例布爾變量的可行解為:獨立變量E5和ER(2,3),派生變量E2、E6、ER(3,2)、ER(3,4)和ER(4,3),半獨立變量E7。根據(jù)基于布爾變量劃分的順序編碼方式和變量編碼賦值規(guī)則,算例的染色體編碼基因鏈如圖3所示。

圖3 算例中染色體編碼基因鏈

2.2.2 遺傳算子

本文針對施工活動和時間關(guān)系間存在的大量邏輯關(guān)系,采用了獨立變量和半獨立變量的順序編碼機制。

1)算子的選擇

調(diào)度模型的目標(biāo)是最小化項目工期,求解過程需要最小化適配值,在選擇過程中將使用輪盤賭的選擇操作,因此,采用項目總工期的倒數(shù)作為適配值。令f(i)表示個體的適配值,在總數(shù)為λ的種群(POP)中個體生存概率為:

(26)

2)交叉算子

本文采用編碼基因鏈單點交叉,即各對應(yīng)編碼基因段分別交叉的方式對個體進行交叉操作。

3)變異算子

本文采用編碼基因鏈基本點位變異。

2.2.3 沖突檢測與消除

傳統(tǒng)遺傳算法采用2種方法求解染色體中存在互相約束的基因編碼問題:

方法1在編碼時剔除掉能夠根據(jù)其他編碼推理得到的變量編碼,之后在適應(yīng)度計算時再對被剔除編碼進行計算,得到適合該染色體的最佳適應(yīng)度值和染色體編碼。

方法2在遺傳操作之后檢測染色體編碼中是否存在沖突的基因編碼,如果存在則將該染色體舍去或者設(shè)置染色體適應(yīng)度值為極低。

在大型復(fù)雜施工項目中,II區(qū)編碼數(shù)量較大,方法1雖然可以降低迭代次數(shù),但每一代種群的求解效率將極低。方法2會產(chǎn)生大量不可行的染色體編碼,導(dǎo)致算法收斂過快,因此,需要設(shè)置比較大的種群數(shù)量來保證種群在整個迭代過程中的多樣性,在工程規(guī)模較大時,求解效率無法令人滿意。

本文算法在進行適應(yīng)度計算之前,依據(jù)I區(qū)獨立變量和II區(qū)其他半獨立變量的約束不等式進行反饋修正II區(qū)基因段,消除違反約束條件的個體。在沖突檢測之后,染色體編碼的I區(qū)獨立編碼部分不受影響,保留原染色體的I區(qū)編碼的有效性,II區(qū)編碼的修改程度依次降低。該修正使II區(qū)部分無效的編碼變?yōu)橛行?同時也保留了有效的編碼區(qū)域。

2.2.4 調(diào)度問題的遺傳算法描述

采用本文遺傳算法計算最短工期的流程如圖4所示。

圖4 遺傳算法計算最短工期的流程

Fig.4 Flowchart of genetic algorithm calculating the shortest construction period

本文遺傳算法的具體實現(xiàn)步驟如下:

步驟1根據(jù)布爾變量順序編碼機制,對調(diào)度模型中的獨立變量和半獨立變量進行順序編碼,并隨機產(chǎn)生初始種群POP,種群規(guī)模為pop,當(dāng)前代數(shù)為GEN=0。

步驟2計算種群中的個體適配值。

步驟3GEN=GEN+1。

步驟4根據(jù)交叉概率參數(shù)Pc,選出參與遺傳操作的子種群POPope,每個個體的染色體由獨立變量基因段和半獨立變量基因段構(gòu)成。

步驟5采用各對應(yīng)編碼基因段分別交叉的方式對POPope中個體進行交叉操作,得到子代種群CHI。

步驟6根據(jù)變異規(guī)則和概率Pm對子代種群CHI中個體的每個基因段進行變異操作。

步驟7將CHI中基因段組合成個體,計算其中個體的適配值。

步驟8POP=POP∪CHI。

步驟9通過選擇操作從POP中選出λ個個體作為下一代的種群。

步驟10檢測II編碼區(qū),依據(jù)I編碼區(qū)獨立變量的約束規(guī)則進行修正。

步驟11如果GEN≥Gmax,終止算法,否則轉(zhuǎn)步驟3。

3 算例仿真

本文在MATLAB(R2015b)下,分別編寫了精確算法與遺傳算法的求解方法。精確解將使用線性求解規(guī)劃器計算得到模型的最短工期解,用于驗證遺傳算法的結(jié)果正確性。遺傳算法的主要參數(shù)如表3所示。

表3 遺傳算法參數(shù)設(shè)置

某后張預(yù)應(yīng)力橋梁采用平衡懸臂法進行施工,2個移動平臺用來支撐在建設(shè)過程中橋墩兩側(cè)的橋梁分段,橋梁結(jié)構(gòu)呈中跨對稱結(jié)構(gòu)。平衡懸臂結(jié)構(gòu)從中間橋墩向兩邊施工的過程中,為保持橋梁結(jié)構(gòu)的穩(wěn)定,在任何時候都必須保證橋梁結(jié)構(gòu)兩邊的澆筑分段數(shù)量之差不大于1 。由于左右平衡懸臂結(jié)構(gòu)的對稱性,本文只研究左邊結(jié)構(gòu)的施工過程,用于測試調(diào)度模型和算法的實用性。本工程共包含25個施工活動,調(diào)度網(wǎng)絡(luò)如圖5所示。

圖5 案例調(diào)度網(wǎng)絡(luò)

通過模型轉(zhuǎn)換引擎,生成混合整數(shù)規(guī)劃模型為:

MinZ=Fp

(27)

其約束條件為:

S1+20≤S2

(28)

S1+20≤S3

(29)

S2+1-(1-ER(2,3))×M≤S3

(30)

S3+1-(1-ER(3,2))×M≤S2

(31)

S2+1≤S4

(32)

S3+1≤S5

(33)

S4+9≤S6

(34)

S5+9≤S6

(35)

S6+1≤S7

(36)

S7+44≤S8

(37)

S7+44≤S9

(38)

S8+1≤S10

(39)

S9+1≤S11

(40)

S10+9≤S12

(41)

S11+9≤S12

(42)

S12+1≤S13

(43)

S12+1≤S14

(44)

S12+1≤S21

(45)

S13+E13≤S15

(46)

S14+E14≤S16

(47)

S15+E13≤S16

(48)

S15+E13≤S19

(49)

S16-(1-E14)×M+9≤S17

(50)

S16+9≤S23

(51)

S17+E14-(1-E14)×M≤S18

(52)

S18+E14-(1-E14)×M≤S19

(53)

S19+1≤S20

(54)

S20+9×E20≤S23

(55)

S21+1≤S22

(56)

S22+9≤S23

(57)

S23+1≤S24

(58)

S24+1≤S25

(59)

ER(2,3)+ER(3,2)=1

(60)

E13+E14=1

(61)

E13≤E20

(62)

E14≤E20

(63)

ER(2,3),ER(3,2),E13,E14,E20∈{0,1}

(64)

Si+Di≤PF,i=1,2,…,n

(65)

Si≥0,i=1,2,…,n

(66)

當(dāng)采用精確算法求解時,計算得出該案例的最短工期為110天。在調(diào)度模型中備擇活動和時間關(guān)系被選擇的情況為E13=1,E14=0,ER(2,3)=1,ER(3,2)=0,ER20=1。

采用遺傳算法求解的結(jié)果如圖6所示。由于本案例活動數(shù)較少,包含的邏輯關(guān)系也較少,在迭代到12代時,整個種群平均天數(shù)已經(jīng)達到最短工期,種群天數(shù)已經(jīng)趨于收斂。計算得到的最短工期仍為110天,案例中布爾變量的計算結(jié)果和精確解相同。

在共228個活動的調(diào)度模型中采用遺傳算法求解,可以發(fā)現(xiàn)在遺傳代數(shù)迭代到45代時,整個種群平均適配天數(shù)已經(jīng)趨于收斂,可得最小工期為689天,和精確解結(jié)果相同。

為驗證設(shè)計的遺傳算法適用于帶有大量邏輯關(guān)系的超大型復(fù)雜調(diào)度模型,本文通過增加邏輯關(guān)系的數(shù)量和項目規(guī)模的來驗證遺傳算法收斂效果。分別在活動數(shù)為500、1 000、2 000的模擬工程仿真中對比精確解、傳統(tǒng)遺傳算法和本文算法的求解效率,其中,傳統(tǒng)遺傳算法A編碼部分將只考慮獨立變量,傳統(tǒng)遺傳算法B將在進行遺傳操作之后對所得染色體進行有效性分析,如果染色體無效將會選擇新的父染色體進行交叉變異操作,計算結(jié)果取3次測試平均值并取整,結(jié)果如表4所示。

表4 模擬案例中的求解效率對比

由表4可以看出,雖然精確解對中小規(guī)模的調(diào)度模型求解速率確實較快,但是隨著工程規(guī)模的擴大,求解效率逐漸弱于本文算法。傳統(tǒng)遺傳算法A受大型工程中約束關(guān)系過多的影響,求解速度極慢,無法在有效時間內(nèi)求解;傳統(tǒng)遺傳算法B對大型工程求解過程中出現(xiàn)交叉變異操作產(chǎn)生的有效染色體概率極低的情況,種群進化速度緩慢,收斂速度降低,在長時間內(nèi)無法得到收斂結(jié)果。

4 結(jié)束語

本文在互斥與共存邏輯關(guān)系的基礎(chǔ)上引入IF-THEN來進一步描述依賴關(guān)系,討論3種邏輯關(guān)系之間的內(nèi)在聯(lián)系,探索更為底層的邏輯關(guān)系表述方法。在此基礎(chǔ)上,擴展調(diào)度模型到混合整數(shù)規(guī)劃模型的轉(zhuǎn)換規(guī)則,并分析邏輯關(guān)系的計算規(guī)則,實現(xiàn)模型間的自動轉(zhuǎn)換。通過對模型中的邏輯關(guān)系變量進行分段編碼,在變異操作后加入沖突檢測環(huán)節(jié),消除由種群初始化與遺傳操作產(chǎn)生的違反約束個體。編程實現(xiàn)本文算法的自動求解,并與精確算法進行對比,仿真結(jié)果表明,隨著工程規(guī)模的擴大,該算法能有效縮短求解工期的時間。下一步將探究染色體編碼中的層級劃分概念,通過改進遺傳算子,在保證近似解合理的情況下提高算法效率。