預制構件生產(chǎn)-運輸-裝配一體化的建造調(diào)度優(yōu)化

秦旋, 朱倩影, 韓家玄

(華僑大學 土木工程學院, 福建 廈門 361021)

傳統(tǒng)建筑業(yè)在施工過程中會產(chǎn)生大量建筑垃圾、噪音和揚塵等污染物,這與我國低碳環(huán)保的發(fā)展理念相悖,亟待向綠色建筑方向轉(zhuǎn)變[1].在此背景下,裝配式建筑得到大力推廣和發(fā)展.目前,預制構件的生產(chǎn)、運輸與裝配3個階段的管理在很大程度上仍依賴于過往經(jīng)驗,缺乏聯(lián)動機制[2],存在調(diào)度不合理、運作效率低、成本居高不下等問題[3].因此,從預制構件生產(chǎn)-運輸-裝配一體化建造出發(fā),優(yōu)化預制構件全階段調(diào)度,對推動我國裝配式建筑發(fā)展具有重要意義.

我國裝配式建筑起步較晚,只有少數(shù)學者將預制構件生產(chǎn)、運輸與裝配3個階段作為一個整體過程進行全階段優(yōu)化研究.Anvari等[4]首次將預制構件全階段的優(yōu)化問題作為擴展型柔性作業(yè)車間調(diào)度(REFJSS)問題,并采用多目標遺傳算法解決REFJSS問題,從而最小化最大完工時間和項目總成本,以及最大化安全性.Khalili等[5]在整個建設周期范圍內(nèi)解決預制構件的調(diào)度問題,將預制構件的生產(chǎn)、運輸與裝配3個階段作為一個完整過程,建立預制構件模塊單元調(diào)度模型,并采用混合整數(shù)線性規(guī)劃(MILP)求解該模型.

目前,對于預制構件調(diào)度優(yōu)化問題,大部分學者根據(jù)流水車間調(diào)度理論進行建模[6-8],并采用啟發(fā)式算法求解該模型.基于此,本文研究預制構件生產(chǎn)-運輸-裝配一體化的建造調(diào)度優(yōu)化.

1 全階段調(diào)度優(yōu)化模型

1.1 預制構件全階段工作流程

裝配式建筑預制構件的生產(chǎn)階段與運輸階段都屬于預制構件的供應鏈范疇,將生產(chǎn)與運輸階段合并成一個擴展的生產(chǎn)過程.預制構件生產(chǎn)-運輸-裝配9 道工序流程,如圖1所示.

圖1 預制構件生產(chǎn)-運輸-裝配9 道工序流程

1.2 混合流水車間調(diào)度問題

混合流水車間調(diào)度問題(HFSP)在流水車間調(diào)度問題(FSP)的基礎上進行擴展[9],FSP工件的每道工序僅對應著一臺固定的加工機器,而HFSP工件的所有或部分工序?qū)嗯_并行機器[10].由于HFSP工件某道工序?qū)娜舾膳_并行機器的屬性是完全相同的,因此,每個并行機器加工該道工序所耗費的時間也是一樣的.

HFSP需要滿足以下4個假設條件:

1) 所有工件的各道工序都可以在對應的任意一臺并行機器上加工;

2) 同一加工階段對應的所有并行機器都是相同的;

3) 某一時刻,一道工序只能在一臺并行機器上加工且不能中斷;

4) 某一時刻,一臺并行機器只能加工一道工序.

混合流水車間調(diào)度問題的加工流程,如圖2所示.圖2中:εk表示第k個工序所對應的并行機器的數(shù)量.E={ε1,ε2,…,εk}表示混合流水車間調(diào)度問題中各工序上并行機器的數(shù)量組合.顯然,當εk=1時,HFSP即轉(zhuǎn)化為FSP.與 FSP類似,HFSP的優(yōu)化目標通常為最小化最大完工時間.

圖2 混合流水車間調(diào)度問題的加工流程

1.3 預制構件全階段調(diào)度優(yōu)化模型

Chan等[11]認為預制構件的生產(chǎn)階段調(diào)度問題本質(zhì)上是屬于FSP.將預制構件的生產(chǎn)-運輸-裝配全階段等效成一個擴展型的生產(chǎn)階段,因此,預制構件的全階段調(diào)度問題也可以等效成HFSP.

1.3.1 基本模型 1) 參數(shù)設置.預制構件全階段調(diào)度的9道工序?qū)狧FSP工件的工序(Nk,k=1,2,…,9);預制構件全階段調(diào)度的單個或單批預制構件對應HFSP工件,把單個或單批預制構件稱為一個作業(yè)(Ji,i=1,2,…,n);與HFSP類似,預制構件全階段調(diào)度的每道工序也對應多臺并行機器(機械設備與人工資源的組合),設jk,m為工序Nk的各并行機器的編號,k=1,2,…,9;tP,Ji,Nk為作業(yè)Ji在工序Nk上的加工處理時間;tP,Ji,Nk,jk為作業(yè)Ji在工序Nk上的第jk,m個機器上的加工處理時間,對于?jk,m,tjk,m≡tP,Ji,Nk,jk,m;tC,Ji,Nk為作業(yè)Ji在工序Nk上的完工時間;tC,max為所有作業(yè)中的最大完工時間.

2) 基本約束條件.引入0-1決策變量XJi,Nk,jk,m,有

(1)

由于一臺并行機器在某一時刻只能加工一道工序,因此有

(2)

同樣地,一道工序某一時刻只能在一臺并行機器上加工,因此有

(3)

各個加工階段的機器按照相同的加工順序加工所有FSP工件,而HFSP工件每道工序都存在若干并行機器,各道工序上不同工件的加工順序是不相同的,因此,不考慮各個作業(yè)之間的順序約束,僅考慮同一作業(yè)內(nèi)工序之間的順序約束,即某工序開始時間不得早于其前面工序的結束時間,有

tC,Ji,Nk≥tC,Ji,Nk-1+tP,Ji,Nk.

(4)

在工序N9(安裝工序)上,不同的作業(yè)滿足一定的安裝順序,某一作業(yè)的安裝開始時間不得早于其前面作業(yè)的安裝結束時間,由此可得到工序N9上作業(yè)執(zhí)行順序的約束條件為

tC,Ji,N9≥tC,Ji-1,Nk+tP,Ji-1,Nk.

(5)

最后,由于各個工序階段對應的并行機器數(shù)量并不是充足的(通常會遠低于作業(yè)的數(shù)量),因此,假設第k個工序Nk對應的并行機器的數(shù)量上限.特別地,在工序N4(養(yǎng)護工序)上,通常所有作業(yè)是可以并行加工的,因此,需考慮養(yǎng)護工序階段具有足夠多的機器.

3) 目標函數(shù).設函數(shù)f1(E)表示作業(yè)的最優(yōu)調(diào)度排序方案對應的最短完工時間,即

f1(E)=min(max(tC,Ji,N9)).

(6)

設函數(shù)f2(E)表示在給定某一種并行機器數(shù)量組合E時,全部并行機器所產(chǎn)生的總成本為

f2(E)=UET

.

(7)

式(7)中:U=(μ1,μ2,…,μ9)T.

特別地,工序N4的機器幾乎不產(chǎn)生成本,因此,令μ4=0,函數(shù)f2(E)可進一步表示為

(8)

全階段調(diào)度模型的最終目標是實現(xiàn)雙目標優(yōu)化,即求解出一種機器數(shù)量組合E和一種調(diào)度排序方案使得函數(shù)f1(E)和函數(shù)f2(E)同時達到最小化.雙目標優(yōu)化問題取值為min(f1(x),f2(x)),x∈Ω,x表示問題的可行解,Ω表示可行解的集合.

1.3.2 雙目標優(yōu)化與熵權法 由于函數(shù)f1(x)和函數(shù)f2(x)分別表示時間和成本,量綱不統(tǒng)一,需要將兩個函數(shù)的值進行統(tǒng)一量綱處理.采用min-max線性歸一化方法將兩個函數(shù)的原始值映射到[0,1]區(qū)間內(nèi),由于函數(shù)f1(x)和函數(shù)f2(x)均為成本型函數(shù)(函數(shù)值越小雙目標優(yōu)化問題越優(yōu)),相應的歸一化函數(shù)為

(9)

式(9)中:歸一化后的函數(shù)F1(x)和F2(x)相當于函數(shù)f1(x)和函數(shù)f2(x)的評價指標,函數(shù)F1(x)和函數(shù)F2(x)值越大,雙目標優(yōu)化問題越優(yōu).

優(yōu)化模型采用線性加權和法將雙目標優(yōu)化問題轉(zhuǎn)化成單目標優(yōu)化問題.轉(zhuǎn)化后的單目標優(yōu)化問題的數(shù)學表達式為

maxF(x)=w1F1(x)+w2F2(x),x∈Ω.

(10)

式(10)中:歸一化后的函數(shù)F(x)為所有可行解的評價函數(shù)(最終的目的是找到函數(shù)F(x)最大的解);w1和w2分別為函數(shù)F1(x)和函數(shù)F2(x)對應的權重,也分別為函數(shù)f1(x)和函數(shù)f2(x)的權重,w1,w2>0,w1+w2=1,且權重通過熵權法確定[11-12].

2 改進的雙種群遺傳算法

遺傳算法是一種典型的元啟發(fā)式算法,通過優(yōu)勝劣汰的方式選擇優(yōu)化問題的最優(yōu)解或近似最優(yōu)解[12-13],是一種高效、并行、隨機的全局搜索尋優(yōu)方法.在求解較為復雜的組合優(yōu)化問題時,相對一些常規(guī)的優(yōu)化算法,遺傳算法能夠快速獲得較好的優(yōu)化結果[14-15].

FSP作為典型的非確定性多項式(NP-hard)問題,應用遺傳算法求解具有非常好的效果[16-18].預制構件全階段調(diào)度模型是基于HFSP進行建模的,因此,遺傳算法也適用于最優(yōu)調(diào)度排序方案的求解.為了提升求解的準確性與效率,對遺傳算法做一些改進.改進的遺傳算法流程圖,如圖3 所示.圖3中:n為迭代次數(shù).

圖3 改進的遺傳算法流程圖

由圖3可知:在改進的遺傳算法流程的循環(huán)體中,交叉操作放在適應度計算步驟之前,也就是每代種群在計算適應度之前都要經(jīng)歷一次交叉操作,而這個交叉操作會產(chǎn)生一個和原種群同樣規(guī)模的新種群(或稱子代種群);新種群與舊種群合并,形成一個雙種群,對雙種群的全部個體適應度進行計算、選擇和變異等;雙種群的進化方式能顯著提高遺傳算法的搜索效率(這是改進后的遺傳算法的最大特點),除了設置雙種群,也改進了算法的編碼方式和交叉方式.

3 仿真案例分析

3.1 案例背景

將某裝配式建筑的某兩個標準層(2F,3F)涉及的預制構件類型和尺寸劃分成 12 個作業(yè),為了貼合實際工程情況,各個作業(yè)在安裝階段都要滿足一定的安裝順序(如 2F 構件要先于 3F 構件安裝).所有構件的養(yǎng)護都采用蒸汽養(yǎng)護方式,并且假設養(yǎng)護窯的數(shù)量足夠多,能夠滿足當前所有構件同時進行養(yǎng)護.構件運輸采用相同的專業(yè)車輛,每輛車一次只能運送一個作業(yè)的構件,構件采用塔吊結合安裝班組(假設安裝班組只有一個)進行安裝.作業(yè)的其他各道工序有若干個相同且獨立的機器設備或人工班組,或二者的組合.各作業(yè)在 9 道工序上的預計加工處理時間,如表1所示.

表1 各作業(yè)在 9 道工序上的預計加工處理時間

規(guī)定工序N9的并行機器的數(shù)量上限為1,工序N7(運輸工序)的并行機器數(shù)量上限為6,工序N4并行機器數(shù)量為L(L是一個足夠大的數(shù),且恒有L>12),其他工序的并行機器數(shù)量上限為3,則并行機器的數(shù)量上限組合E=[3,3,3,L,3,3,6,3,1].假設N1至N9各道工序上每臺機器的成本已知,令U=[5.0,7.0,10.0,0,5.0,6.0,0.5,5.0,15.0]為各道工序上總機器成本組合,其中,成本為無量綱.

3.2 全階段調(diào)度優(yōu)化問題的求解

3.2.1 最優(yōu)調(diào)度排序方案的求解 采用 MATLAB軟件進行編程,采用改進的雙種群遺傳算法求解仿真案例的最優(yōu)作業(yè)調(diào)度排序方案.除了已知的加工時間矩陣和機器數(shù)量組合E之外,其他參數(shù)的設置如下:最大迭代次數(shù)為100;種群規(guī)模為80;變異概率為0.95;情況1～情況3的并行機器數(shù)量組合分別為E1=[1,1,1,L,1,1,1,1,1],E2=[2,2,2,L,2,2,2,2,1],E3=[3,3,3,L,3,3,6,3,1].令L=50,得到各代最優(yōu)個體適應度曲線和最優(yōu)作業(yè)調(diào)度排序方案甘特圖,分別如圖4,5所示.圖4,5中:tC,min為適應度(最短完工時間).

(a) 情景1 (b) 情景2 (c) 情景3

由圖4可知:情景1在第1次迭代時就已經(jīng)得到最小適應度(81.2 h),此后的迭代都收斂于相應的最優(yōu)值;情景2在第20次迭代時得到最小適應度(55.4 h),此后的循環(huán)迭代中每代種群中的最優(yōu)值都為該值;情景3在第3次迭代時就收斂到了最小適應度(53.8 h),此后的迭代最優(yōu)值都為該值.

由圖5可知:情景1的各道工序(除工序N4外)的并行機器數(shù)量都設為1,在這種特殊的機器數(shù)量組合下,各作業(yè)的調(diào)度順序呈現(xiàn)很強的規(guī)律性,同時,這種情況下最優(yōu)完工時間在所有不同組合情況中是最長的,該調(diào)度方案也可作為其他情況的對照方案;相比于情景1,情景2的并行機器數(shù)量擴大了一倍,相應的最短完工時間也大大縮短了25.8 h,且最優(yōu)調(diào)度方案是不固定的,可存在多個最優(yōu)解,沒有明顯的規(guī)律性,在工序N9上的作業(yè)加工順序都嚴格滿足相應約束條件;相比于情景2,情景3的并行機器的數(shù)量雖然增加了不少,但最短完工時間縮短了1.4 h,這說明當并行機器的數(shù)量足夠多時,繼續(xù)增加并行機器帶來的時間收益會越來越小;在規(guī)定的機器數(shù)量上限以內(nèi),存在一個或多個機器數(shù)量組合的臨界點,同時,也存在某種機器數(shù)量組合能使最短完工時間和總機器成本都最小化.

(a) 情景1 (b) 情景2 (c) 情景3

3.2.2 雙目標優(yōu)化問題的求解 雙目標優(yōu)化問題的目的是尋找一種或多種并行機器的數(shù)量組合,最大化獲取“時間+成本”的綜合收益,即最小化最短完工時間和總機器成本.首先,需要確定并行機器數(shù)量組合的種類數(shù)量,為了精簡求解范圍,假設工序N7,N8,N9的并行機器數(shù)量是固定的,分別為6,3,1,令工序N4的并行機器數(shù)量L=50.因此,并行機器數(shù)量組合的種類與剩下5道工序的機器數(shù)量取值有關,并且該5道工序的機器數(shù)量上限皆為3,則并行機器數(shù)量組合共有 35=243 種(按 1 至 243 的順序?qū)Σ⑿袡C器的所有數(shù)量組合進行編號).

根據(jù)已知的總機器成本組合U=[5.0,7.0,10.0,0,5.0,6.0,0.5,5.0,15.0]及并行機器數(shù)量組合E=[a,b,c,50,d,e,6,3,1](a,b,c,d,e=1,2,3),采用MATLAB軟件進行編程,求解每種機器數(shù)量組合下的函數(shù)f1(x)和函數(shù)f2(x),最終得到243對值.最短完工時間函數(shù)和總機器成本函數(shù)的散點圖,如圖6所示.

圖6 最短完工時間函數(shù)和總機器成本函數(shù)的散點圖

由圖6可知:離散點在縱軸上分層明顯,表明在某一固定總成本下,不同的機器數(shù)量組合帶來的時間收益可能會大相徑庭;幾乎每一個函數(shù)f1(x)的值都對應著許多個函數(shù)f2(x)的值,并且函數(shù)f2(x)的值跨度較大,這表明在時間目標固定時,可以通過改變并行機器數(shù)量組合降低成本;越靠近左下角的離散點越優(yōu).

利用min-max公式,對所求的243對值進行歸一化處理,得到相應的評價因子指標函數(shù)F(x)值(F1(x)值,F2(x)值).根據(jù)F(x)值,利用熵權法,采用MATLAB軟件進行編程,求解得到的F1(x)指標權重為w1=0.832,F2(x)指標權重為w2=0.168,指標權重w1,w2也是雙目標優(yōu)化中目標函數(shù)f1(x)和f2(x)的權重.

最短完工時間函數(shù),總機器成本函數(shù)與評價因子指標函數(shù)三維散點圖,如圖7所示.由圖7可知:越靠近左上角的離散點越優(yōu).根據(jù)權重值w1,w2及函數(shù)F1(x),F2(x)值,利用線性加權和公式F(x)=w1F1(x)+w2F2(x),最終可以求得評價因子指標函數(shù)F(x)值.

圖7 最短完工時間函數(shù)和總機器成本函數(shù)與評價因子指標函數(shù)三維散點圖

243種機器數(shù)量組合與相應評價因子指標函數(shù)二維散點圖,如圖8所示.由圖8可知:越靠上的點(函數(shù)F(x)值越大),其對應的并行機器數(shù)量組合越優(yōu).

圖8 243種機器數(shù)量組合與相應評價因子指標函數(shù)二維散點圖

評價因子指標函數(shù)對應的主要指標值,如表2所示.由表2可知:并行機器數(shù)量組合E=[2,3,2,50,1,1,6,3,1]的評價因子指標函數(shù)F(x)的值最大,也是雙目標優(yōu)化問題的最優(yōu)解,函數(shù)f1(x)的值為

表2 評價因子指標函數(shù)對應的主要指標值

54,函數(shù)f2(x)值為95.

最優(yōu)機器數(shù)量組合下的最優(yōu)調(diào)度方案甘特圖,如圖9所示.

圖9 最優(yōu)機器數(shù)量組合下的最優(yōu)調(diào)度方案甘特圖

4 結論

根據(jù)裝配式建筑的整個建造過程,分析研究預制構件在生產(chǎn)、運輸與裝配階段的具體工作流程,對各個階段的工作流程進行簡化,將預制構件全階段的工作流程簡化為9道工序.將預制構件調(diào)度優(yōu)化作為一個擴展型的生產(chǎn)車間調(diào)度優(yōu)化問題.在HFSP理論的基礎上,對預制構件全階段調(diào)度問題進行建模,對完工時間和并行機器的總機器成本進行優(yōu)化.采用改進的遺傳算法對模型求解,改進后的遺傳算法更符合模型要求,并提高了搜索最優(yōu)解的效率.

對預制構件生產(chǎn)-運輸-裝配全階段調(diào)度進行優(yōu)化,打破以往研究中只考慮某一個階段的局限性,促進裝配式建筑更加經(jīng)濟化、合理化、科學化.但也存在一些不足,如模型的約束多是基于多種理想化的假設,沒有充分考慮實際工程情況,以及在模型多目標優(yōu)化時沒有優(yōu)化其他成本.