基于遺傳算法的突發情況分段吊裝順序調整

李二虎， 楊 敏

(江蘇科技大學 船舶與海洋工程學院， 江蘇 鎮江 212003)

0 引 言

企業初始吊裝作業在計劃的執行過程中可能會遇到很多突發情況。分段延遲到達、設備故障、惡劣天氣等突發情況會對作業計劃的實施進程造成影響，情況嚴重時甚至會影響交船日期。針對突發情況，林垚君[1]提出基于混合粒子群算法的重調度算法，但其運行結果并沒有保證初始船臺周期。續愛民[2]采用分支定界法對擾動后的分段吊裝順序進行調整，但其研究只是針對單船合龍而言。為了提高船臺使用效率，企業通常采用多艘船舶并行建造的方式，如圖1所示。在該建造方式下，當發生突發情況時，僅憑調度人員的工作經驗來調整初始吊裝方案，不僅難以保證船臺周期，而且不利于船臺資源的均衡使用。本文在工期固定-資源均衡理論的基礎上，采用改進遺傳算法調整突發情況受擾動分段的吊裝順序，從而在保證初始船臺周期不變的前提下，均衡使用船臺資源。

圖1 船舶在船臺上同時合龍現場

1 問題描述及模型的構建

1.1 問題描述

分段延遲到達、設備故障、惡劣天氣等突發情況會影響吊裝作業計劃的順利實施，如果處理不當，則可能耽誤生產進度，延誤交船時間。與延誤交船時間相比，企業從其他部門調配資源相對容易，因此大部分企業為了保證船臺周期，通常通過增加船臺資源數量的方式，對受擾動后分段的吊裝順序進行調整[3]，其實質是將初始作業計劃中由于資源數量約束而被迫推遲吊裝的分段盡可能提前開工，以保證生產節點。但是具體做法往往是由調度人員憑借經驗和作業進度對增加的資源進行安排，這種人工調度方式不僅難以合理配置資源，而且還會經常出現趕工期而加班的情況。根據實際工作特點，本文采用項目調度問題中工期固定-資源均衡理論建立突發情況分段吊裝順序調整模型。該理論采用資源數量不受限制的方式，通過調整由于資源約束而未能實施的項目的開工時間，在限定工期內均衡使用資源[4]。對于突發情況分段吊裝過程，本文假設為惡劣天氣導致的吊裝作業計劃停滯。在惡劣天氣時，一方面增加焊機和人力資源的數量，另一方面調整受擾動分段的作業順序，從而在吊裝作業后期保證節點，均衡使用資源。

本文采用改進遺傳算法動態調整在惡劣天氣時多艘船舶的分段吊裝順序，主要分為以下4個步驟：

(1) 計算初始船臺周期。根據企業初始吊裝方案，計算船臺周期。

(2) 重新繪制吊裝網絡圖。惡劣天氣發生后，將吊裝完成的分段從初始網絡圖中剔除，重新繪制未吊裝分段的吊裝網絡圖。

(3) 確定新的吊裝工期。為保證初始船臺周期，將新工期設置為原始工期和惡劣天氣發生后的開工時間之差。

(4) 優化分段吊裝順序。在部分船臺資源數量不受限制的前提下，采用改進遺傳算法優化多艘船舶的分段吊裝順序，合理安排其開始時間。

1.2 模型的構建

工期固定-資源均衡理論對資源均衡強度的評價指標通常有不均衡系數K、資源均衡極差ΔR和資源均衡方差σ2等[5]。本文采用資源均衡方差σ2來判定限定船臺周期的船臺資源使用是否均衡。

假設惡劣天氣發生時，在船臺并行建造的n艘船舶均沒有完成合龍，第i(i=1,2，…，n)艘船的新工期為Ti，需要調整吊裝順序的分段數有Si個。吊裝過程中使用m種資源，船臺能夠提供第k(k=1,2，…，m)種資源的數量是Rk。Aij表示第i艘船的第j個分段，其緊前吊裝任務集合是Pij，最早開始吊裝時間是TEij，最晚開始吊裝時間是TLij，實際開始吊裝時間是TSij，作業時間是dij，單位時間內對資源k的需求量是rijk，I(t)表示t時刻正在進行的吊裝活動集合，λk表示第k種資源的權重系數，則多艘船舶分段吊裝順序調整模型表示如下：

目標函數為

(1)

約束條件為

TEij≤TSij≤TLij

(2)

TSij-TSih≥dih, ?h∈Pij

(3)

其中：i=1,2,…，n;j=1,2,…，Si

Rkt≤Rk

(4)

λ1+λ2+λ3+…+λm=1

(5)

式(1)是目標函數，表示m種資源的方差加權和最小。式 (2)～式(5)是約束條件。式(2)表示分段的開工時間必須介于最早和最晚開始時間之間；式(3)表示分段工藝約束，分段Aij必須在其緊前分段吊裝完成之后才可以開始作業；式(4)表示t時刻所有分段對吊車的需求量不得超過船臺所能提供的總量。式(4)中Rkt表示所有船舶的所有分段在同一工作時間t時刻對資源k的需求量。由于吊車屬于大型設施，同焊機和人力不同，其數量在短時間內不可變化，因此式(4)特別針對吊車而言。式(5)表示m種資源的權重系數和為1。

2 基于遺傳算法的分段吊裝順序調整模型求解

分段吊裝順序優化是典型的NP-hard問題。由于問題復雜，數學規劃及分支定界等傳統優化方法已不再適用。遺傳算法是美國HOLLAND教授在生物模擬技術的啟發下提出來的一種借鑒生物界自然選擇和遺傳機制的隨機搜索算法，已成功應用于求解作業調度問題方面[6]。本文采用改進遺傳算法求解惡劣天氣時多艘船舶的分段吊裝順序調整問題，旨在通過遺傳算法的整體尋優特性，實現限定船臺周期下資源的均衡使用。

2.1 遺傳算法的改進

由于分段數目眾多，約束復雜，針對標準遺傳算法采用固定參數導致算法不易收斂等不足，本文提出動態確定種群規模和交叉變異概率，使其隨著算法進程自適應調整，從而削弱算法對固定參數的依賴性，改善算法性能[7]。

對于種群規模，分別從微觀和宏觀兩個角度對其調整。微觀方面，借鑒ARABAS等[8]提出的對個體引入“年齡”和“壽命”的方法，規定個體產生時具有一定壽命且年齡為零。在迭代過程中，首先計算個體壽命，復制一定數量的個體，同時年齡加1，然后淘汰年齡超過壽命的個體，最后對剩余個體進行交叉變異,并將新產生的個體插入種群。個體壽命采用公式(6)進行計算，其中：fs(i)為個體適應度值；lt(i)為個體壽命；FB,FW,FA分別是當前種群中最好、最差和平均適應度；maxTL和minTL分別是個體的最大和最小壽命。

若fs(i)≤FA，則lt(i)

若fs(i)>FA，則lt(i)

(6)

宏觀方面，從限制復制個體數量的角度對種群規模加以控制[9]。復制個體的數量采用公式(7)進行計算,式中:Sp,c(t+1)為t+1代復制的個體數量；Sp(t)和Sp(0)分別是第t代和初始種群的數量；R1和R2是復制比。

(7)

對于交叉和變異概率，本文根據個體年齡和壽命的關系分別通過式(8)和(9)確定。

(8)

(9)

式(8)中：Pc是交叉概率；Pcmax，Pcmin分別是最大和最小交叉概率；lamax，lamin，laavg分別是當前種群中個體的最大、最小和平均剩余代數；la′是兩交叉個體中較大的剩余代數。剩余代數指個體壽命和年齡之差。式(9)中：Pm是變異概率；Pmmax，Pmmin分別是最大和最小變異概率；la是變異個體的剩余代數。

2.2 遺傳操作的設計

(1) 染色體編碼。根據問題特點，本文采用實數編碼方式，以分段的實際開工時間為基因值。具體做法是：首先將1艘船的各個分段按照分段序號進行編碼，形成子染色體串；然后將n艘船舶所有子染色體串按照船舶序號依次連接，形成1條染色體。在上述模型中，共有S(S=S1+S2+…+Si)個分段需要進行編碼，則染色體的長度為分段總數S，1條染色體可以表示為

RCH={TS11,TS12,…,TS1S1,TS21,TS22,…,TS2S2,…,TSi1,TSi2,…,TSiSi}

(2) 初始化種群。初始化種群需要考慮2個因素：①各分段的開始吊裝時間介于最早和最晚開始時間之間；②各分段要滿足工藝約束，即只有在其緊前分段吊裝完成之后才可以開始作業。

針對第①點，首先分別計算出各分段最早和最晚開始吊裝時間。最早開始吊裝時間TSij應該沿著新的吊裝網絡圖正向計算，最晚開始吊裝時間TLij須根據新的船臺周期在吊裝網絡圖中反向計算。則分段的實際開始吊裝時間為：TSij=TEij+rand(0,(TLij-TEij))。

針對第②點，需要對分段的開始吊裝時間進行修復。根據分段工藝約束，檢查其開始吊裝時間，對不滿足的分段重新賦值。

(3) 確定適應度函數。適應度函數由目標函數采用公式(10) 轉換而來，式中：fs(t)是適應度函數；fsmax和fsmin分別是當前種群中最大和最小目標函數值；fs是當前個體的目標函數值。φ是0～1的正實數，設置它是為了防止上式被零除。

(10)

(4) 選擇、交叉和變異操作。在個體迭代過程中，分別采用式(6)和式(7)計算個體壽命和復制的個體數量，淘汰其中年齡超過壽命的個體，實現種群中個體的選擇操作。采用單點交叉方式，交叉概率Pc通過式(8)計算得出。采用均勻變異方式，變異概率Pm通過式(9)計算得出。

對于交叉和變異之后產生的非法個體，采用類似種群初始化時個體修復方法對其進行修復，檢查個體所代表分段的開始吊裝時間是否滿足工藝約束，淘汰其中不滿足的個體，同時將新產生的個體添加到種群中。

3 實例分析與驗證

本節以企業4艘船舶的吊裝方案為背景。首先根據初始吊裝方案，計算船臺周期；然后在工期固定-資源均衡理論的基礎上采用改進遺傳算法對擾動后的分段吊裝順序進行調整；最后通過與企業初始吊裝方案進行對比，驗證該方法對于解決惡劣天氣下多艘船舶分段吊裝順序調整問題的合理性和可行性。

3.1 實例介紹

4艘船舶在船臺的布置情況如圖2所示。1號和2號船并聯布置在1號船臺，共用吊車M1和M2；3號和4號船并聯布置在2號船臺，共用吊車M3和M4。吊車的吊運能力均是300 t。4艘船舶為3 900 TEU集裝箱船，采用橫向下水方式。該船共有245個分段，中組之后，每艘船在船臺搭載的分段數目為39個。圖3為吊裝網絡圖，表示分段工藝約束，矩形框內表示分段編碼，各分段采用塔式建造法在滿足工藝約束的要求下依次進行合龍。

圖2 4艘船舶在船臺的布置情況

圖3 3 900 TEU集裝箱船吊裝網絡圖

為便于編碼操作，同時便于遺傳算法程序語言的編寫，依次對各分段進行簡化編號。1～39，40～78，79～117，118～156分別表示1，2，3，4號船的各個分段。對于船臺資源，本文只考慮吊車、焊機和人力3種。根據企業實際情況，船臺可提供的使用總量分別是4座、6臺和45人。以1號船為例，表1給出分段簡化序號與分段編碼的對應關系、分段作業時間以及對船臺資源的需求情況。

表1 3 900 TEU集裝箱船分段吊裝數據

3.2 優化過程及結果

按照企業初始吊裝方案，4艘船舶各分段的開始吊裝時間如表2所示。1,2,3,4號船的吊裝完成時間分別為335 h,509 h,515 h,535 h。如果按照1周6天、1天8 h的工作制折算，4艘船舶的船臺周期分別為47天、5天、76天、80天。

表2 初始吊裝方案4艘船各分段的開始吊裝時間 h

初始吊裝方案的部分船臺派工計劃如表3所示。由該表得出整個工作周期內吊車、焊機和人力的使用效率分別為72.5%，86.9%和70.4%。

表3 初始吊裝方案部分船臺派工計劃 h

假設在第240 h時由于惡劣天氣導致吊裝作業計劃不得不停滯10 h，此時，4艘船舶均沒有完成合龍，其中：1號船已吊裝分段28個，剩余11個；2號船已吊裝分段11個，剩余28個；3號船已吊裝分段18個，剩余21個；4號船已吊裝分段14個，剩余25個。因此，需要重新調整吊裝順序的分段數目為85個。以1號船為例，圖4表示惡劣天氣發生時合龍工作的完成情況，其中：虛線框內表示已完成吊裝分段；實線框內表示未開始吊裝分段。

圖4 惡劣天氣發生時1號船分段合龍完成情況

根據求解步驟，首先匯總4艘船中未開始吊裝的分段，繪制吊裝網絡圖，然后確定新的船臺周期。根據惡劣天氣發生時間以及4艘船各分段初始吊裝完成時間，計算得出4艘船新的船臺吊裝工期依次是85 h， 259 h，265 h和285 h。由前文可知，4艘船統一優化時，船臺吊裝工期為285 h。最后，根據工期固定-資源均衡理論，建立惡劣天氣多艘船舶分段吊裝順序調整模型，并通過MATLAB編程求解。參數設置如下：初始種群規模SP(0)=200，個體最大壽命maxTL=8,最小壽命minTL=2，最大交叉率Pcmax=0.9,最小交叉率Pcmin=0.4,最大變異率Pmmax=0.01,最小變異率Pmmin=0.000 1,復制率R1=0.4，R2=0.2。吊車M1/M2,M3/M4,焊機和人力的權重系數分別是0.3，0.3，0.2，0.2，最大迭代次數為200代。

統計結果表明，50次試驗中，4種資源的資源均衡方差收斂于區間[41.253，44.312]，方差的最大偏離值為(44.312-41.253)/41.253=7.4%。取其中一次計算結果整理如表4所示，結合分段對船臺資源的需求量和資源權重系數，計算得出4種資源的使用方差分別為0.873 5，0.741 7，5.239 7，205.344 5，加權和為42.601 4。由表4可以看出，經過調整優化之后，4艘船舶均可在初始船臺周期內完工，沒有因為惡劣天氣而延誤船臺周期。改進遺傳算法的進化曲線如圖5所示。該結果說明，本文采用改進遺傳算法求解多艘船舶分段吊裝順序動態調整時的資源均衡問題總能收斂到一個近似最優解。

圖5 改進遺傳算法進化曲線

表4 調整后各分段的吊裝順序及其開始吊裝時間 h

由初始派工計劃可知，惡劣天氣發生在施工第36天。受到天氣影響，第36天的吊裝作業必須停滯。因此，從第37天開始，制定第250 h～535 h的實際派工計劃，合理安排每天須吊裝的分段數目，同時為吊裝任務分配船臺資源。表5列出了惡劣天氣后的部分船臺派工計劃。

表5 惡劣天氣后部分船臺派工計劃

為便于與初始吊裝方案對比，分別以吊車、焊機和人力各自每天需求量繪制柱狀圖，橫軸表示吊裝工期，縱軸表示資源需求數量。圖6表示惡劣天氣發生后工期內吊車的使用情況。由于吊車數量在短時間內不可變化，因此，惡劣天氣發生后，面對“時間緊，任務重”的生產現狀，需要更加注重吊車的協調安排，提高其使用效率。由圖6可以看出，在整個吊裝工期內，吊車的使用數量沒有超過資源上限。整個工期內，由于天氣影響和企業正常工作時間安排，吊裝作業時間為68天。通過計算，船臺能夠提供的吊車總量為272座，而分段實際對吊車的需求量為198座，吊車的使用效率為72.8%。

圖6 吊車在吊裝工期內的使用情況

圖7和圖8分別表示焊機和人力的使用情況。惡劣天氣發生后，本文采用適當增加焊機和人力數量的方法，將原本由于資源數量不足而被迫推遲作業的分段提前開工，從而在保證初始船臺周期不變的同時均衡使用船臺資源。由圖7和圖8可以看出：第38,40,41,43,44,51,64,67,73,75天使用的焊機數量超過了船臺初始能夠提供的焊機數量最大值6臺；第40和48天使用的人力數量超過了船臺初始能夠提供的人力數量最大值45人。在這些時間段內，總裝部門需要臨時從其他部門調配適當數量的焊機和人力來配合完成船臺合龍工作。通過計算，吊裝工期內船臺能夠提供的焊機總量和人力重量分別為408臺和3 060人，而分段實際對焊機和人力的需求量為368臺和2 269人，兩者的使用效率分別為90.2%和74.2%。

圖7 焊機在吊裝工期內的使用情況

圖8 人力在吊裝工期內的使用情況

3.3 結果分析

表6列出初始吊裝方案和動態調整方案下的吊裝工時和3種船臺資源使用效率的對比情況。由表6數據可以看出，本文采用改進遺傳算法求解惡劣天氣分段吊裝順序調整方案，不僅可以保證初始船臺周期不變，而且在一定程度上提高船臺資源的使用效率。該方法可以為企業在面對突發情況時順利實施吊裝作業計劃提供一種新的解決方案。

表6 吊裝工時和資源使用效率對比

4 結 論

本文首先在工期固定-資源均衡理論的基礎上建立多艘船舶分段吊裝順序調整數學模型，然后針對標準遺傳算法的不足，提出從動態確定種群規模與交叉變異概率的角度改進算法性能，并根據多船分段吊裝過程的特點，設計編碼方法、種群初始化等遺傳操作，最后給出基于改進遺傳算法求解4艘船舶分段吊裝順序調整實例。通過與企業初始吊裝方案對比，驗證該方法對于解決分段吊裝順序動態調整問題是合理和可行的，可為企業在突發情況下順利實施船臺吊裝作業計劃提供一種新的解決方案。

[1] 林垚君.考慮不確定性的復雜裝備制造作業流程重調度研究及其應用[D].杭州:浙江大學，2014.

[2] 續愛民.船臺吊裝過程調度優化關鍵技術研究[D].上海:上海交通大學，2008.

[3] 杭立杰.船臺吊裝順序優化關鍵技術研究[D].哈爾濱:哈爾濱工程大學，2009.

[4] 鄧莎.工期固定條件下的多項目資源平衡問題研究[D].長沙:湖南大學，2007.

[5] 李欣.基于蟻群算法的軟件行業工期固定-資源均衡優化決策及其實現[D].重慶:重慶大學，2015.

[6] 李政,方舟，吳權.應用于船舶型材套料的遺傳算法關鍵技術[J].造船技術,2017(4):24-27.

[7] 謝力,魏汝祥.基于自適應遺傳算法的總體艦船維修費用分配[J].船海工程,2006,35(1):58-60.

[8] ARABAS J，MICHALEWICZ Z,MULANKA J et al. GAVaPS-a genetic algorithm with varying population size[C]//IEEE Conference on Evolutionary Computation,1994(1):73-78.

[9] 鄧軼婧.基于改進自適應遺傳算法的多項目資源優化問題研究[D]. 天津:河北工業大學，2013.