基于遺傳算法的突發(fā)情況分段吊裝順序調(diào)整

李二虎， 楊 敏

(江蘇科技大學(xué) 船舶與海洋工程學(xué)院， 江蘇 鎮(zhèn)江 212003)

0 引 言

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

圖1 船舶在船臺上同時合龍現(xiàn)場

1 問題描述及模型的構(gòu)建

1.1 問題描述

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

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

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

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

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

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

1.2 模型的構(gòu)建

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

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

目標(biāo)函數(shù)為

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

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

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

2.1 遺傳算法的改進(jìn)

由于分段數(shù)目眾多，約束復(fù)雜，針對標(biāo)準(zhǔn)遺傳算法采用固定參數(shù)導(dǎo)致算法不易收斂等不足，本文提出動態(tài)確定種群規(guī)模和交叉變異概率，使其隨著算法進(jìn)程自適應(yīng)調(diào)整，從而削弱算法對固定參數(shù)的依賴性，改善算法性能[7]。

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

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

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

(6)

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

(7)

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

(8)

(9)

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

2.2 遺傳操作的設(shè)計

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

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

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

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

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

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

(10)

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

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

3 實例分析與驗證

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

3.1 實例介紹

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

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

圖3 3 900 TEU集裝箱船吊裝網(wǎng)絡(luò)圖

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

表1 3 900 TEU集裝箱船分段吊裝數(shù)據(jù)

3.2 優(yōu)化過程及結(jié)果

按照企業(yè)初始吊裝方案，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所示。由該表得出整個工作周期內(nèi)吊車、焊機和人力的使用效率分別為72.5%，86.9%和70.4%。

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

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

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

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

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

圖5 改進(jìn)遺傳算法進(jìn)化曲線

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

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

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

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

圖6 吊車在吊裝工期內(nèi)的使用情況

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

圖7 焊機在吊裝工期內(nèi)的使用情況

圖8 人力在吊裝工期內(nèi)的使用情況

3.3 結(jié)果分析

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

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

4 結(jié) 論

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

[1] 林垚君.考慮不確定性的復(fù)雜裝備制造作業(yè)流程重調(diào)度研究及其應(yīng)用[D].杭州:浙江大學(xué)，2014.

[2] 續(xù)愛民.船臺吊裝過程調(diào)度優(yōu)化關(guān)鍵技術(shù)研究[D].上海:上海交通大學(xué)，2008.

[3] 杭立杰.船臺吊裝順序優(yōu)化關(guān)鍵技術(shù)研究[D].哈爾濱:哈爾濱工程大學(xué)，2009.

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

[5] 李欣.基于蟻群算法的軟件行業(yè)工期固定-資源均衡優(yōu)化決策及其實現(xiàn)[D].重慶:重慶大學(xué)，2015.

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

[7] 謝力,魏汝祥.基于自適應(yīng)遺傳算法的總體艦船維修費用分配[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] 鄧軼婧.基于改進(jìn)自適應(yīng)遺傳算法的多項目資源優(yōu)化問題研究[D]. 天津:河北工業(yè)大學(xué)，2013.