船舶分段涂裝并行施工調(diào)度優(yōu)化

劉 濤， 姚志榮

(上海江南長興造船有限責(zé)任公司， 上海 201913)

0 引 言

隨著國內(nèi)外各大船廠對殼舾涂一體化造船模式的研究和應(yīng)用，傳統(tǒng)的整體造船法將生產(chǎn)作業(yè)物量遺留至船塢和碼頭階段進(jìn)行施工的方式，現(xiàn)已逐步被舾裝前移、分段涂裝、總組舾裝和涂裝完整性施工的分段式生產(chǎn)方式所替代，大幅降低船塢和碼頭的施工周期，提高對總組平臺的利用率，提高船塢吊車吊裝效率，從而提高造船企業(yè)整體的生產(chǎn)效率[1]?；诜侄蔚拇爸圃炝鞒倘鐖D1所示。船舶分段涂裝建造過程因自身存在不穩(wěn)定因素，使在造船生產(chǎn)計劃中分段涂裝計劃的編制和優(yōu)化更加困難，因此需要對船舶分段涂裝的業(yè)務(wù)流程和計劃管理流程進(jìn)行分析。本文以國內(nèi)某造船廠為背景對船舶分段涂裝業(yè)務(wù)流程和計劃管理模式進(jìn)行分析，對船舶分段涂裝施工調(diào)度問題進(jìn)行研究，為后續(xù)船舶分段涂裝項目調(diào)度優(yōu)化研究奠定基礎(chǔ)。

圖1 基于分段的船舶制造流程

1 船舶分段涂裝施工業(yè)務(wù)流程

1.1 船舶分段涂裝生產(chǎn)流程

船舶分段涂裝在整個船舶制造過程中起著承上啟下的作用，是拉動前道分段物量完成和保證后道搭載節(jié)點的關(guān)鍵，因此在整個船舶制造過程中，分段階段需完成對主船體75%的涂裝作業(yè)工作量[2]。船舶制造中的分段涂裝生產(chǎn)流程如圖2所示。

圖2 船舶分段涂裝生產(chǎn)流程

1.2 現(xiàn)代造船企業(yè)生產(chǎn)計劃管理流程

現(xiàn)代造船企業(yè)的生產(chǎn)計劃管理流程是自上而下分階段逐步分解的過程，主要分為線表計劃、大日程計劃、中日程計劃和小日程計劃。

船舶分段涂裝的生產(chǎn)計劃管理是在船舶建造總進(jìn)度計劃指導(dǎo)下的小日程計劃：根據(jù)前道部門雙月滾動計劃確定分段到達(dá)的開始作業(yè)時間；根據(jù)后道搭載部門的雙月滾動總組搭載計劃，確定分段配送的需求時間；涂裝部門根據(jù)當(dāng)前在制分段生產(chǎn)情況和跨間、勞動力等資源負(fù)荷情況，制定分段涂裝部門的生產(chǎn)計劃。由上至下分為5層，如圖3所示。一級計劃為公司雙月滾動計劃(分段涂裝計劃，見圖4)，二級計劃為部門月計劃，三級計劃為作業(yè)區(qū)雙周滾動計劃(見圖5)，四級計劃為單船周計劃，五級計劃為班組日計劃。

作業(yè)區(qū)周計劃為部門各施工作業(yè)區(qū)依據(jù)部門雙月滾動計劃，編制各生產(chǎn)作業(yè)區(qū)周度項目的開工和完工計劃，主要用于對作業(yè)區(qū)承擔(dān)各號船施工項目完成雙周滾動計劃所需資源和周期進(jìn)行反饋調(diào)整，對生產(chǎn)進(jìn)度和資源消耗進(jìn)行控制協(xié)調(diào)。

圖3 船舶制造業(yè)涂裝生產(chǎn)計劃管理流程圖

2 船舶分段涂裝項目網(wǎng)絡(luò)計劃

2.1 船舶分段涂裝項目網(wǎng)絡(luò)計劃模型

對船舶分段涂裝的分級網(wǎng)絡(luò)計劃制定分級網(wǎng)絡(luò)計劃模型，該模型采用自頂向下的方式將項目計劃逐層細(xì)分，直至項目被完全分解為只包含任務(wù)不包含任何子網(wǎng)絡(luò)計劃的末級網(wǎng)絡(luò)計劃[3]，以上海某大型造船廠為背景，將項目計劃共分為5層分級網(wǎng)絡(luò)計劃。

分級網(wǎng)絡(luò)計劃模型為

P={P11,…，P1i,…，P1n,A11,…，A1j,…，A1m,S1,E1|i=1,…,n1，j=1,…,m1}，其中每個P1i可進(jìn)一步分解為由ni個網(wǎng)絡(luò)計劃P2ij與mi個任務(wù)T2ik及其之間的關(guān)系集A2i、開始節(jié)點S2i和結(jié)束節(jié)點E2i構(gòu)成的二級網(wǎng)絡(luò)計劃，即

P1i={P2ij,…，P2ij,…，P2in,T2i1,…,T2ik,…,T2im,A2i,S2i,E2i|j=1,…,ni，k=1,…,mi},采用上述方式對項目計劃逐層分解，直至達(dá)到5層分級網(wǎng)絡(luò)計劃。船舶分段涂裝分級網(wǎng)絡(luò)計劃模型建立過程如圖6所示。

圖7展示了船舶分段涂裝分級網(wǎng)絡(luò)計劃的建立流程。

2.2 船舶分段涂裝分級網(wǎng)絡(luò)計劃模型優(yōu)化

船舶制造企業(yè)中船舶分段涂裝生產(chǎn)計劃是按照線表計劃逐級編制的，越往下分解包含的對象任務(wù)越少，對其進(jìn)行優(yōu)化效果不明顯，因此需對底層網(wǎng)絡(luò)計劃進(jìn)行合并。將作業(yè)過程中資源需求相似或作業(yè)工序相近的同級網(wǎng)絡(luò)計劃合并成虛擬父級計劃并進(jìn)行優(yōu)化，再將虛擬父級計劃還原至子網(wǎng)絡(luò)計劃中，保證原子網(wǎng)絡(luò)計劃任務(wù)對象的邏輯關(guān)系未改變，同時將具體任務(wù)對象的開始結(jié)束時間進(jìn)行優(yōu)化[4]，形成虛擬的分級網(wǎng)絡(luò)計劃模型，如圖8所示。

3 基于遺傳算法的船舶分段涂裝并行施工周期優(yōu)化

對分段涂裝生產(chǎn)調(diào)度的業(yè)務(wù)流程分析后發(fā)現(xiàn)，在其調(diào)度過程中存在的主要問題是周期優(yōu)化問題和資源均衡優(yōu)化問題。船舶涂裝分段制造過程通常是多船型分段并行生產(chǎn)作業(yè)，在作業(yè)過程中對沖砂跨間、油漆跨間、人力、分段堆場等資源的使用優(yōu)先級是相同的，因此在船舶分段涂裝生產(chǎn)過程中計劃安排的合理性將直接影響每個分段施工過程對資源的使用，若發(fā)生某些意外事件(如跨間設(shè)備發(fā)生損壞、連續(xù)下雨、班組人員流失等)，還會導(dǎo)致項目整體周期的拖延，因此調(diào)度過程主要考慮2方面問題[5]：

(1) 在船舶分段涂裝生產(chǎn)過程中，如何在緊前關(guān)系約束和資源約束的前提下使各分段總體施工周期達(dá)到最短，即資源-周期最短化調(diào)度優(yōu)化問題。

(2) 對船舶分段涂裝調(diào)度優(yōu)化得到最優(yōu)周期后，如何使各分段施工工序間對資源的利用率得到提升，對勞動力、跨間等資源利用均衡化，即周期-資源均衡調(diào)度優(yōu)化問題。

雖然這2類調(diào)度優(yōu)化問題在一般工程項目中有較多研究討論，但針對船舶制造過程中涂裝過程的調(diào)度優(yōu)化研究較少,現(xiàn)對船舶分段涂裝周期和資源均衡優(yōu)化問題進(jìn)行研究。

3.1 船舶分段涂裝并行施工周期優(yōu)化問題模型

船舶制造企業(yè)按照網(wǎng)絡(luò)計劃方式進(jìn)行計劃管理，通過在網(wǎng)絡(luò)計劃圖底層網(wǎng)絡(luò)對象任務(wù)中增加虛擬開始/結(jié)束作業(yè)的方式，將號船分段涂裝施工對象的網(wǎng)絡(luò)計劃進(jìn)行合并，形成帶作業(yè)周期和資源需求量的虛擬網(wǎng)絡(luò)計劃圖[6]，如圖9所示。

圖4 部門雙月滾動計劃流程圖

圖5 部門雙周滾動計劃流程圖

圖6 船舶分段涂裝分級網(wǎng)絡(luò)計劃模型

圖7 船舶分段涂裝分級網(wǎng)絡(luò)計劃的建立流程

圖8 優(yōu)化后的船舶分段涂裝生產(chǎn)分級網(wǎng)絡(luò)計劃模型

圖9 虛擬網(wǎng)絡(luò)計劃圖

圖9中：ni為第i個作業(yè)的作業(yè)編號；r1i和r2i分別為第i個作業(yè)在單個工作日對R1、R2等2種資源的消耗量；di為第i個作業(yè)的周期；S、E分別為合成項目的虛擬開始和結(jié)束作業(yè)；s1、e1、s2、e2分別為項目1、2 的虛擬開始和結(jié)束作業(yè)；ds1、ds2、de1、de2分別為虛擬作業(yè)s1、e1、s2、e2對應(yīng)的周期[7]。

船舶分段涂裝項目工期優(yōu)化問題包含m個并行項目，共享k種可更新資源(其中第k種資源的供給上限為Rk),第i個項目包含ni+2個作業(yè)(其中第0個和第ni+1個作業(yè)為項目i的虛擬開始和結(jié)束作業(yè)，具有一定的持續(xù)時間但不消耗任何資源)。第i個項目中的第j個作業(yè)記為Aij,其工期為dij，開始時間記為Sij,h為第i個作業(yè)的時間，對第k種資源的需求量為Rijk,用Pij表示作業(yè)Aij的緊前作業(yè)集合，It表示第t個工作日正在進(jìn)行的所有作業(yè)集合，則問題的數(shù)學(xué)模型可以描述為

(1)

(2)

Sij≥Sih+dih,?h∈Pij,?i,j

(3)

(4)

rijk≥0

(5)

(6)

式(1)為目標(biāo)函數(shù)，表示所有項目的最短加權(quán)總工期，i表示第i個項目的權(quán)重；式(2)指并行項目的權(quán)重系數(shù)之和必須為1；式(3)為項目作業(yè)的緊前關(guān)系約束，作業(yè)開始前必須保證其緊前作業(yè)集中的所有作業(yè)均已完工；式(4) 為資源約束，在單個工作日內(nèi)所有作業(yè)對某一資源的需求量之和必須小于該資源的供給上限；式(5)指作業(yè)對任一資源的需求均不得為負(fù)；式(6) 為第t個工作日正在進(jìn)行的所有作業(yè)集合。

對上述船舶分段涂裝調(diào)度優(yōu)化問題數(shù)學(xué)模型進(jìn)行如下假設(shè):

(1) 分段開始進(jìn)跨沖砂作業(yè)直至油漆完工交驗；

(2) 對于跨間設(shè)備、堆場場地等資源的使用，各施工班組共享；

(3) 在單位時間內(nèi)各資源供給可滿足生產(chǎn)需求；

(4) 各號船分段油漆施工工序相互獨立；

(5) 不考慮天氣、分段脫期供應(yīng)等因素。

3.2 船舶分段涂裝并行施工周期優(yōu)化問題模型求解

3.2.1 船舶分段涂裝并行施工周期優(yōu)化問題算法的求解思路

在船舶分段涂裝并行施工工期優(yōu)化問題中作業(yè)對象較多，隨著分段數(shù)目逐步增加，染色體的長度變大，使問題解的空間變大，造船種群的多樣性變小(問題解空間變大，而種群規(guī)模卻不變)，易使問題收斂至小范圍內(nèi)的局部最優(yōu)解，找不到全局最優(yōu)解，從而出現(xiàn)早熟問題[8]。在分層遺傳算法的基礎(chǔ)上融入模擬退火算法思想，構(gòu)成模擬退火分層遺傳算法。模擬退火算法能以一定概率接受劣解，具有很強的局部搜索能力，可以彌補遺傳算法局部尋優(yōu)能力弱的問題，幫助算法跳出局部最優(yōu)解[9]，同時還可對遺傳算法的交叉算子和變異算子進(jìn)行模擬退火操作，達(dá)到與自適應(yīng)遺傳算法類似的目的，這樣融合可有效地提高分層遺傳算法的局部尋優(yōu)能力和質(zhì)量，形成船舶分段涂裝并行施工調(diào)度問題模型算法的求解思路。模擬退火分層遺傳算法的流程如圖10所示。

3.2.2 基于遺傳算法的模擬退火分層遺傳算法設(shè)計

基于遺傳算法的模擬退火分層遺傳算法在低層和高層遺傳算法進(jìn)化過程中，不進(jìn)行免疫操作，直接采用模擬退火處理后的交叉概率Pc和變異概率Pm,進(jìn)行交叉和變異操作，避免算法早熟，及時將低層算法結(jié)果傳輸至高層遺傳算法，確保每運行一代都進(jìn)行終止判斷，如果不滿足終止條件，繼續(xù)高層遺傳算法，當(dāng)進(jìn)化5代后，返回低層遺傳算法進(jìn)行新一輪的尋優(yōu)。

(1) 染色體編碼

染色體編碼方式采用任務(wù)列表的形式進(jìn)行，其表達(dá)式為Vk=[r1,r2,…,ri,…,rmn] ，其中mn為總?cè)蝿?wù)數(shù)，ri為第i個任務(wù)。

(2) 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)為f(s)=1 /F(s) ，其中：F(s)為個體s的目標(biāo)函數(shù)值。

(3) 初始化種群

一般遺傳算法均采用隨機方式生成初始種群，但對本文研究的問題采用常規(guī)隨機化方式生成初始化種群不太合適，主要原因是無法滿足作業(yè)緊前關(guān)系約束。如何進(jìn)行初始化將直接影響初始種群的好壞，最終影響優(yōu)化算法的整體計算效率和最優(yōu)解質(zhì)量[10]。

圖10 模擬退火分層遺傳算法流程圖

(4) 解碼操作

周期優(yōu)化問題是利用每個作業(yè)的具體開始時間去求解對應(yīng)的施工周期，對具體作業(yè)的周期進(jìn)行優(yōu)化，但在染色體中只包含作業(yè)本身固有的邏輯作業(yè)關(guān)系，并不包含作業(yè)本身具體的作業(yè)開始時間，因此染色體需要進(jìn)行解碼操作。

假設(shè)有m個作業(yè)工序，Ti表示作業(yè)i的周期，Sj表示作業(yè)j的開始時間，染色體Vk=[r1,r2,…,ri,…,rmn] 表示經(jīng)過優(yōu)化后的作業(yè)排序列表，則對該染色體的解碼進(jìn)行如下操作：

Step 1：令S1= 0,j= 1；

Step 2：當(dāng)j≤mn時，j=j+ 1，轉(zhuǎn)Step 3，否則轉(zhuǎn)Step 6；

Step 3：Sj= max{Sk+dk}(k∈Pj) ，轉(zhuǎn)Step 4；

Step 4：判斷各資源在作業(yè)j的持續(xù)時間內(nèi)是否存在沖突， 若存在則轉(zhuǎn) Step 5，否則轉(zhuǎn)Step 2；

Step 5：Sj=Sj+ 1，轉(zhuǎn)Step 4；

Step 6：返回所有作業(yè)的開始時間，結(jié)束。

求得各項目周期為

Ti=Si(n i+1)-Si1

(7)

加權(quán)后項目的總周期為

T=∑?iTi

(8)

(5) 模擬退火操作

① 基于遺傳算法的模擬退火操作，自適應(yīng)的Pc、Pm函數(shù)實現(xiàn)其表達(dá)式為

(9)

(10)

式中：num為最大進(jìn)化代數(shù)；T1為進(jìn)化代數(shù)的倒數(shù)。在進(jìn)化初期T1較高、Pc較大，有利于結(jié)合優(yōu)良基因，交叉產(chǎn)生更多優(yōu)秀個體，而Pm較小，因為進(jìn)化初期變異操作不起主要作用；隨著進(jìn)化代數(shù)的增加，T1逐漸減小，Pc逐漸減小，避免過多的無用交叉，提高算法效率，而Pm則逐漸增大，有利于產(chǎn)生新個體，增加種群多樣性，幫助種群跳出局部最優(yōu)解。

② 交叉和變異后個體的模擬退火操作

在交叉和變異操作后個體Vi的鄰域N內(nèi)隨機選取一個問題的一點Vi1(Vi1也是問題的一個可行解)，隨機生成[0,1]之間的數(shù)q，判斷Pt(T2) 是否大于q，若大于則用Vi1代替Vi，否則保留Vi[8]。

(11)

式中：f(Vi1)和f(Vi)為個體的適應(yīng)度值；fmax為初始種群個體的最大適應(yīng)度值；T2為進(jìn)化代數(shù)；Pt(T2)隨著進(jìn)化代數(shù)的增加不斷減小，使算法在進(jìn)化前期接受惡解而在后期則只接受好解。

3.3 船舶分段涂裝并行施工周期優(yōu)化問題實例分析

以上海某大型造船廠分段涂裝施工項目作為實例進(jìn)行分析，以不同船舶間分段的2個相同部位的壓載艙作為研究對象，項目1.1表示集裝箱船分段A的壓載艙區(qū)域涂裝施工(使用中途油漆配套)，項目1.2表示散貨船分段B的壓載艙區(qū)域涂裝施工(使用佐敦油漆配套)，對網(wǎng)絡(luò)計劃模型中作業(yè)關(guān)系相似、資源需求相近的底層網(wǎng)絡(luò)計劃作業(yè)工序進(jìn)行合并，添加虛擬作業(yè)時間，確保各分段涂裝施工工序的開始時間和作業(yè)邏輯關(guān)系保持不變，形成新的虛擬父級網(wǎng)絡(luò)圖。船舶分段涂裝并行施工項目單代號網(wǎng)絡(luò)計劃如圖11所示。

圖11 船舶分段涂裝并行施工項目單代號網(wǎng)絡(luò)計劃圖

本例求解的是在資源約束下優(yōu)化船舶分段涂裝施工項目工期，其中分段A和分段B的權(quán)重系數(shù)分別為0.6和0.4，資源R1和資源R2的供給上限分別為40和33，算法參數(shù)設(shè)置為種群數(shù)量=90,子種群個數(shù)C=3，最大進(jìn)化代數(shù)num=80,獨立進(jìn)化代數(shù)num=5,交叉變異概率Pc和Pm根據(jù)式(9)和式(10)動態(tài)改變。

由式(7)計算，項目1.1的分段A優(yōu)化后的周期為T1=S30+S4=31，項目1.2的分段B 優(yōu)化后的周期為T2=S31+S5=31 ，加權(quán)后的項目總周期為T1=?iT1+?2T2= 31,如表1所示。

表1 并行分段作業(yè)調(diào)度優(yōu)化后的開始時間

通過對此問題模型分別采用標(biāo)準(zhǔn)遺傳算法(GA)和 SAHGA 方法進(jìn)行計算求解并對比結(jié)果，以證明本文提出的算法對問題的優(yōu)化效果，各進(jìn)行50 次迭代計算過程后，可知本文采用的SAHGA算法較一般遺傳算法對問題最優(yōu)解求解效率更高，并且具有更好的收斂性。調(diào)度優(yōu)化后的計算結(jié)果對照如表1和表2所示。

從表 2 可知，利用SAHGA算法在求解船舶分段涂裝周期調(diào)度算法在50次運算中，有46次找到最優(yōu)解31.0，求解效率也更高(平均26次迭代計算)。

表2 GA和SAHGA方法優(yōu)化結(jié)果比較

4 結(jié) 論

從宏觀角度對整個船舶制造流程進(jìn)行分析說明，對船舶分段涂裝施工業(yè)務(wù)流程和涂裝施工計劃管理進(jìn)行梳理分析，應(yīng)用網(wǎng)絡(luò)計劃管理方法建立船舶分段涂裝施工分級網(wǎng)絡(luò)計劃模型，并對分級網(wǎng)絡(luò)計劃模型的特點進(jìn)行說明，通過船舶生產(chǎn)實際情況將底層網(wǎng)絡(luò)計劃進(jìn)行優(yōu)化處理，最后對船舶分段涂裝并行施工調(diào)度所要解決的問題點進(jìn)行梳理，明確船舶分段涂裝并行施工項目調(diào)度優(yōu)化的研究方向，即主要針對船舶分段涂裝周期優(yōu)化問題進(jìn)行研究。通過對船舶分段涂裝施工周期優(yōu)化問題進(jìn)行描述，建立周期優(yōu)化問題的數(shù)學(xué)模型，應(yīng)用求解算法對該問題進(jìn)行求解分析，引用了基于遺傳算法的SAHGA。該算法以船舶分段涂裝施工項目總周期最小化為目標(biāo)，在種群的初始化和解碼過程中考慮作業(yè)緊前關(guān)系約束和資源約束，保證每種作業(yè)工序的排序都成為可行的調(diào)度方案，使研究問題得到簡化；然后引用遺傳算法分層思想，避免遺傳算法中“早熟”現(xiàn)象發(fā)生；最后通過在算法中引入模擬退火的思路，改善算法對問題最優(yōu)解的求解效率；最終通過船廠分段涂裝生產(chǎn)實例驗證表明本文提出的SAHGA對船舶分段涂裝周期的調(diào)度優(yōu)化相比遺傳算法效果更明顯，更易滿足船舶分段涂裝的生產(chǎn)周期需求。