王 家,金艷琪，陳雅含

(湖南大學 土木工程學院，湖南 長沙 410082)

0 引言

預制構(gòu)件生產(chǎn)是裝配式建造推廣的重要環(huán)節(jié)之一，在預制構(gòu)件生產(chǎn)過程中，涉及到人力、材料、機械等多方面。隨著我國建造領(lǐng)域工業(yè)化的不斷推進[1]，對預制構(gòu)件的需求量不斷增長，對預制構(gòu)件的質(zhì)量要求也不斷上升[2]。而目前我國預制構(gòu)件生產(chǎn)加工廠普遍存在技術(shù)管理人員專業(yè)化技術(shù)和產(chǎn)業(yè)化實施能力不足的問題[3]，這一現(xiàn)狀使得預制構(gòu)件呈現(xiàn)出總體生產(chǎn)成本較高，總體環(huán)境效益不顯著的弊端。預制構(gòu)件生產(chǎn)目標均衡的目的在于為預制構(gòu)件的生產(chǎn)工序選擇合適的生產(chǎn)執(zhí)行模式組合，科學合理地根據(jù)構(gòu)件生產(chǎn)需求制定生產(chǎn)方案，提高預制構(gòu)件生產(chǎn)效率，降低預制構(gòu)件生產(chǎn)成本，增強預制構(gòu)件的環(huán)境效益，從而促進裝配式建筑行業(yè)的高質(zhì)量發(fā)展。

預制構(gòu)件生產(chǎn)過程中的目標均衡優(yōu)化問題有著復雜的含義。從目標考慮，可以分為成本優(yōu)化問題[4-5]、效率優(yōu)化問題[6-7]、碳排放優(yōu)化問題[8-9]和庫存優(yōu)化問題[10]等,以及不同類型優(yōu)化目標的組合優(yōu)化問題。從算法考慮，可以分為精確算法求解問題和啟發(fā)式算法求解問題。精確算法主要基于動態(tài)規(guī)劃、整數(shù)規(guī)劃、分支界定等方法[11]，而啟發(fā)式算法主要基于遺傳算法[12-13]、蟻群算法[14]、粒子群算法[15-16]、共生生物搜索算法[17]等算法。預制構(gòu)件生產(chǎn)目標均衡問題的復雜程度隨著工序數(shù)量的增加而急劇上升，因此，針對工序數(shù)量較多的預制構(gòu)件生產(chǎn)目標均衡問題，精確算法并不適用，只能采用啟發(fā)式算法。但是，現(xiàn)有啟發(fā)式算法具有隨機性，在最優(yōu)解獲取穩(wěn)定性上仍有較大的改進空間。

為此，本文針對預制構(gòu)件生產(chǎn)目標均衡優(yōu)化問題，提出一種基于子集模擬的啟發(fā)式優(yōu)化算法。利用聚集函數(shù)法，將生產(chǎn)時間、成本和生產(chǎn)過程中產(chǎn)生的碳排放納入優(yōu)化目標，構(gòu)建多模式下預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型。同時為了增強子集模擬在全局范圍的搜索能力，采取均勻間隔取點的馬爾科夫鏈方法，增加樣本點的多樣性。通過實際案例的驗證，與改進的遺傳算法相比，本文提出的優(yōu)化算法在最優(yōu)解獲取的穩(wěn)定性上有較好改進。

1 預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型

考慮包含n道工序，每道工序i(i=1,2,…,n)涉及mi種生產(chǎn)執(zhí)行模式的預制構(gòu)件生產(chǎn)項目。該項目中第i道工序的第j(i=1,2,…,mi)種執(zhí)行模式的持續(xù)時間、耗費成本和產(chǎn)生的碳排放分別表示為tij,cij和eij。預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型中，一般通過指示變量Xij表示工序i所選擇的執(zhí)行模式，如工序i選擇第j種執(zhí)行模式，則Xij=1。因各工序僅能選擇一種執(zhí)行模式，指示變量需滿足如下約束條件：

(1)

項目的調(diào)度方案，可表示為包含所有指示變量的矩陣X={Xij,i=1,…,n,j=1,mi}。例如，表1為某生產(chǎn)項目目標均衡方案的矩陣表示，該項目包含5道工序，每道工序?qū)膱?zhí)行模式總數(shù)分別為4、2、4、4和3。由指示變量Xij的含義可知，該項目調(diào)度方案中，工序1～5所選擇的執(zhí)行模式分別為第2、第1、第3、第3和第2。

表1 典型目標均衡方案的矩陣表示Table 1 Matrix representation of typical resource schedu-ling scheme工序i執(zhí)行模式j(luò)123410100210——30010400105010—

在給定項目調(diào)度方案X={Xij,i=1,…,n,j=1,mi}下，生產(chǎn)項目的工期T(X)可通過調(diào)度方案X中各工序執(zhí)行模式的生產(chǎn)時間累加得出，如式(2)所示：

(2)

式中:L表示關(guān)鍵路徑上工序的集合。同理，可以求出生產(chǎn)項目的總制造成本C(X)和總碳排放量E(X)：

(3)

(4)

預制構(gòu)件生產(chǎn)均衡優(yōu)化的目標, 是通過對工序執(zhí)行模式的合理組合，盡可能實現(xiàn)項目工期、成本和碳排放量的最小化.為綜合考慮工期、成本和碳排放量3項子目標，本文將各子目標無量綱化，并分配反映重要性程度的權(quán)重系數(shù)，進而建立如下的優(yōu)化模型：

(5)

s.t.

T(X)≤T*,C(X)≤C*,E(X)≤E*

其中,Tmin，Cmin，Emin為各子目標的下限值；Tmax，Cmax，Emax為各子目標的上限值;w1,w2,w3為各子目標在模型中的權(quán)重系數(shù)；本文采用層次分析法確定，T″，C″，E″分別為各子目標的最大容許值。

生產(chǎn)項目的調(diào)度方案，也可采用向量的表示形式θ=(θ1,θ2,…,θn)。此時,向量θ中的元素θi,i=1,…,n代表工序i的執(zhí)行模式，為[1,mi]內(nèi)的自然數(shù)。由項目調(diào)度方案的矩陣表示X與向量表示θ的含義可知,X與θ間存在一一對應關(guān)系.例如，表1的矩陣表示X，對應工序1～5分別選擇第2、第1、第3、第3和第2執(zhí)行模式的調(diào)度方案, 其向量表示為θ=(2,1,3,3,2)。利用X與θ間的一一對應關(guān)系X=X(θ)，可得調(diào)度方案向量表示下的優(yōu)化模型：

(6)

s.t.

T(θ)≤T*,C(θ)≤C*,E(θ)≤E*

式(4)的優(yōu)化模型為離散型優(yōu)化模型，某些情形下針對其等價的連續(xù)性優(yōu)化模型進行求解更為方便.式(4)的優(yōu)化模型中，決策變量θi,i=1,…,n為[1,mi]內(nèi)的自然數(shù), 可針對其引入(0,1]間取值的連續(xù)性決策變量ui,i=1,…,n, 并建立兩者間的函數(shù)關(guān)系如下：

θi=ceil(ui×mi),0

(7)

式中:函數(shù)ceil()為向右取整函數(shù)。此時，預制構(gòu)件生產(chǎn)調(diào)度優(yōu)化模型可以表示為連續(xù)型決策變量U=(u1,u2,…,un)下的優(yōu)化模型：

(8)

s.t.

T(θ(U))≤T*,C(θ(U))≤C*,E(θ(U))≤E*0

2 基于子集模擬的生產(chǎn)調(diào)度優(yōu)化算法

子集模擬法(Subset Simulation)是 Au 和 Beck 提出的，針對結(jié)構(gòu)可靠度問題的高效數(shù)值模擬算法[18]。其思想是通過引入一系列中間失效事件，將偶發(fā)事件的小概率表示為一系列較大的條件概率乘積, 進而將小概率估計問題轉(zhuǎn)化為一組較大的條件概率的估計問題[19]，以提高數(shù)值模擬算法的計算效率。通過利用可靠度問題和優(yōu)化問題的內(nèi)在聯(lián)系，子集模擬方法在優(yōu)化設(shè)計問題中也取得了較好的應用[20]。

2.1 基于子集模擬的生產(chǎn)目標均衡優(yōu)化算法框架

考慮如下優(yōu)化問題：

minf(U)

(9)

s.t.

0

T(U)≤T*,C(U)≤C*,E(U)≤E*

為利用子集模擬法求解上述優(yōu)化問題，人為設(shè)定變量U為隨機變量，服從可行域Ω0={U∶0f2>…,fJ，可在可行域Ω0內(nèi)定義一系列逐漸收縮的區(qū)域Ωj={U∶U∈Ω0,f(U)≤fj},j=1,…,J。 此時，所考察的區(qū)域間存在子集關(guān)系，Ω0?Ω1?Ω2…?ΩJ，這也是子集模擬法名稱的由來。通過依次在可行域Ω2與逐漸收縮區(qū)域Ωj(j=1,…J)內(nèi)按均勻分布進行隨機取樣，子集模擬法可逐漸縮窄搜索區(qū)域，最終在最優(yōu)解附近的較小區(qū)域內(nèi)進行搜索，以得到問題的最優(yōu)解。

2.2 可行域Ω0內(nèi)均勻分布樣本點的產(chǎn)生

a.在區(qū)域Ω={U∶0

考慮到預制構(gòu)件生產(chǎn)優(yōu)化問題中變量U的維數(shù)(對應項目中的工序數(shù)量)較大，本文采用改進Metropolis-Hasting方法[17]，以完成上述馬爾科夫鏈中的迭代操作。具體而言，方法采用一維均勻分布的概率密度分布函數(shù)p*(ξ/u)作為建議概率密度分布函數(shù)。該函數(shù)以u為中心，以d為寬度(即u-d/2≤ξ≤u+d/2)(d一般取0.2～0.4)，可自動滿足對稱性的要求。馬爾可夫鏈中Uk=(uk,1,uk,2,…,uk,n)到Uk+1=(uk+1,1,uk+1,2,…,uk+1,n)的迭代操作如下：

2.3 收縮區(qū)域Ωj={U∶U∈Ω0,f(U)≤fj}內(nèi)均勻分布樣本點的產(chǎn)生

如2.1節(jié)所述，基于子集模擬的優(yōu)化算法中，需根據(jù)在收縮區(qū)域Ωj內(nèi)的少量樣本點，利用MCMCS方法產(chǎn)生要求數(shù)量的樣本點。方法中具體的馬爾科夫鏈迭代操作與2.2節(jié)類似，但需額外考慮收縮區(qū)域的邊界限制f(U)≤fj，因此，需將2.2節(jié)馬爾科夫鏈迭代操作中的步驟修改如下：

在實際運算過程中，為了避免MCMCS產(chǎn)生的樣本點陷入局部最優(yōu)，采用均勻間隔取點的方式，每間隔e個狀態(tài)點選擇一點作為樣本點。如圖1所示。以p0=0.1,M=100,e=3為例，當Uk作為一條鏈條的起點時，如果采取連續(xù)取點的方法，那么需要通過MCMCS方法產(chǎn)生(1/p0-1)=9個狀態(tài)點，這些點全部作為樣本點。此時，馬爾科夫鏈長度為10。如果間隔取點，則需要產(chǎn)生[1/p0×(e+1)-1]=39個狀態(tài)點，此時，馬爾科夫鏈長度為40。取第5,9,13,…,37個點作為樣本點。通過間隔取點的方法，產(chǎn)生的樣本點更具有多樣性。

(a) 連續(xù)取點的馬爾科夫鏈

2.4 基于子集模擬的預制構(gòu)件生產(chǎn)目標均衡優(yōu)化算法總結(jié)

針對以上預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型，本文基于子集模擬法，建議的優(yōu)化算法步驟總結(jié)如下：a.確定子集模擬算法中的參數(shù)，即在指定區(qū)域中抽樣的樣本數(shù)量M、條件概率參數(shù)p0、改進Metropolis-Hasting方法中定義一維均勻概率分布的寬度d和MCMCS中均勻間隔取點數(shù)e。

e.算法采用的迭代終止原則為達到預先設(shè)定的迭代次數(shù)J。如不滿足迭代終止條件，即j>J，令j=j+1，重復步驟4。

3 案例分析

以文獻[21]中某預制構(gòu)件廠一預制構(gòu)件生產(chǎn)線為例，該生產(chǎn)線包含21道生產(chǎn)工序，如圖2所示。每道工序?qū)?jié)約、正常、趕工3種執(zhí)行模式，每種執(zhí)行模式下對應的生產(chǎn)時間、花費成本和產(chǎn)生的碳排放量如表2所示。受到外界資源限制，最大生產(chǎn)時間閾值T*=540 min，最高生產(chǎn)成本閾值C*=2 600元，最大生產(chǎn)碳排放閾值E*=800 kg(碳排放指二氧化碳當量，全文同)。

圖2 某預制構(gòu)件生產(chǎn)流程圖

需要注意的是，工序7、12、13為非關(guān)鍵工序，不計入生產(chǎn)總時間。根據(jù)表2，可以計算出僅考慮單個資源消耗的理想值Tmax=640 min,Cmax=2 769元，Emax=818.37 kg;Tmax=509 min,Cmax=2 556元，Emax=790.03 kg。利用層次分析法，通過專家打分，各資源的相對權(quán)重確定為[w1,w2,w3]=[0.2,0.2,0.6]。

表2 各工序時間成本碳排放量匯總Table 2 Summary of carbon emissions of each process time cost序號工序節(jié)約模式正常模式趕工模式時間/min成本/元碳排放/kg時間/min成本/元碳排放/kg時間/min成本/元碳排放/kg1清理模板、預埋件、臺車面25973.10201052.51171112.162模具檢驗7190.025220.03———3劃線———5130.25———4邊模組裝12320.0710440.098350.075復核尺寸7190.025220.03———6涂脫模油7150.065150.05———7工裝與材料準備(非關(guān)鍵工序)25583307.8420604307.8815607307.98布筋、綁扎、固定251520.76201550.78181700.819布置脫模吊釘、吊具201220.18151170.18131230.210布筋檢驗10270.035220.03———11布置預埋件204680.12154710.14124730.1112混凝土攪拌(非關(guān)鍵工序)———10443452.278460460.1413混凝土輸送(非關(guān)鍵工序)———5130.61———14混凝土布料、振搗20376.7215405.0410443.3715表面檢查、清理8150.015180.02———16趕平、抹光12222.4110272.028351.6417養(yǎng)護42042003603605.64———18構(gòu)件反向、落平、轉(zhuǎn)移———154010.410446.9619表面磨光12220.210270.347310.4720脫模15407.6410445.128494.1221吊裝入庫———102711.688289.36

為檢驗基于子集模擬的目標均衡優(yōu)化算法的性能，每代隨機抽樣樣本取M=1 000，條件概率參數(shù)取p0=0.1，篩選產(chǎn)生初始樣本點數(shù)量取t=10，改進Metropolis-Hasting方法中一維均勻概率分布的寬度取d=0.30，MCMCS中均勻間隔取點數(shù)取e=3。圖3描述了基于子集模擬的建議優(yōu)化算法一次典型求解過程中，最優(yōu)目標函數(shù)值隨迭代階段的變化。由圖3可知，算法經(jīng)過4次迭代后收斂到最優(yōu)解，對應最優(yōu)目標函數(shù)值0.212 9。該最優(yōu)解對應的各工序執(zhí)行模式的選擇如表3所示，對應生產(chǎn)時間T=534 min，花費成本元C=2 598元，產(chǎn)生的碳排放量E=796.42 kg。

圖3 建議優(yōu)化算法典型求解過程中最優(yōu)目標函數(shù)值隨迭代階段的變化

為檢驗基于子集模擬的建議優(yōu)化算法的穩(wěn)定性，設(shè)計了改進的遺傳算法( Improved Genetic Algorithm,IGA)進行對比。經(jīng)過試驗，傳統(tǒng)的GA無法在相對有限的時間內(nèi)，隨機產(chǎn)生足夠數(shù)量滿足約束條件的初始樣本點。因此，運用2.2節(jié)中的方法對初始種群的產(chǎn)生方法進行處理，得到改進后的遺傳算法(IGA)。考慮到交叉概率參數(shù)pc和變異概率參數(shù)pc對 IGA 算法求解的影響，本文進行了大量pc和pm組合取值，檢驗發(fā)現(xiàn)，交叉概率pc=0.9和變異概率pm=0.05下，IGA 算法求解本案例目標均衡問題的性能最優(yōu)，因此表4給出的是這組交叉概率和變異概率下IGA 算法的對比結(jié)果。同時，考慮到計算資源對2種優(yōu)化算法的影響，結(jié)合兩種算法的特點，在子集模擬算法中，每代樣本點取1 000，迭代終止條件為最優(yōu)解連續(xù)3次迭代保持不變，再將子集模擬實際的運算量作為IGA的迭代終止條件。

表3 典型最優(yōu)解對應的各工序執(zhí)行模式選擇與各資源消耗量Table 3 Selection of the execution mode of each process corresponding to the typical optimal solution and the consumption of each resource工序執(zhí)行模式工序執(zhí)行模式工序執(zhí)行模式12(正常)82(正常)151(節(jié)約)21(節(jié)約)92(正常)162(正常)31(正常)102(正常)172(正常)41(節(jié)約)113(趕工)182(趕工)51(節(jié)約)121(正常)191(節(jié)約)62(正常)131(正常)203(趕工)71(節(jié)約)143(趕工)212(趕工)

表4提供了2種算法1 000次獨立運行求解獲得的最優(yōu)目標函數(shù)值的統(tǒng)計結(jié)果(最小值、平均值、最大值和標準差)。對比可知，基于子集模擬的優(yōu)化算法獲得最優(yōu)目標函數(shù)值的平均值為0.213 0，小于基于 IGA 的優(yōu)化算法的相應數(shù)值(0.213 5)，且最優(yōu)目標函數(shù)值的標準差值更小。此外，圖4給出了2種算法 1 000 次獨立運行獲得的最優(yōu)目標函數(shù)值的分布情況。由圖4可見，基于子集模擬的優(yōu)化算法性能更優(yōu)，其獲得的最優(yōu)目標函數(shù)值分布更為集中，有96.2%的最優(yōu)目標函數(shù)值集中在(0.212 0，0.213 0]區(qū)間，表明基于子集模擬的建議優(yōu)化算法獲取最優(yōu)解的穩(wěn)定性更高。

表4 基于子集模擬的優(yōu)化算法與 IGA 算法獨立運行 1 000 次獲得的最優(yōu)目標函數(shù)值的統(tǒng)計結(jié)果Table 4 The statistical results of the optimal objective function value obtained by the optimization algorithm based on the subset simulation and the IGA algorithm independently run 1 000 times算法最優(yōu)解的目標函數(shù)值統(tǒng)計最小值平均值最大值標準差基于子集模擬的優(yōu)化算法0.212 90.213 00.215 82.682 7E-04基于IGA的優(yōu)化算法0.212 90.213 50.225 20.001 3

圖4 兩種優(yōu)化算法獨立運行 1 000 次獲得的最優(yōu)目標函數(shù)值的分布

4 結(jié)論

本文針對預制構(gòu)件生產(chǎn)項目的目標均衡優(yōu)化問題，基于子集模擬法進行啟發(fā)式優(yōu)化算法的研究，主要研究結(jié)論如下：

a.在構(gòu)建預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型時，引入權(quán)重系數(shù)，對多個優(yōu)化目標進行處理，并通過映射條件，將離散型變量問題轉(zhuǎn)化為連續(xù)型變量求解問題。

b.針對預制構(gòu)件生產(chǎn)目標均衡優(yōu)化模型，提出基于子集模擬的建議優(yōu)化算法，并給出算法框架和具體操作步驟。

c.為產(chǎn)生滿足約束條件的初始種群，采用隨機產(chǎn)生和MCMCS相結(jié)合的方法，先篩選少量滿足約束的初始樣本點，再以MCMCS的方法擴充至整個初始種群，提高計算效率。

d.為避免收縮區(qū)域內(nèi)樣本點產(chǎn)生陷入局部最優(yōu)，采取均勻間隔取點的馬爾科夫鏈方法，增強子集模擬在全局范圍的搜索能力，豐富種群的多樣性。

e.通過算例驗證，與改進的遺傳算法相比，基于子集模擬的建議優(yōu)化算法在最優(yōu)解的獲取穩(wěn)定性上有較大改進。