基于仿真的船舶分段建造動態空間調度

王津劍　杜吉旺　范秀敏,2　何其昌,2

1.上海交通大學,上海,200240　2.上海市網絡化制造與企業信息化重點實驗室,上海,200240

?

基于仿真的船舶分段建造動態空間調度

王津劍1杜吉旺1范秀敏1,2何其昌1,2

1.上海交通大學,上海,2002402.上海市網絡化制造與企業信息化重點實驗室,上海,200240

為縮小船舶分段空間調度計劃與實際作業安排之間的差別，提出了一種基于仿真的船舶分段建造動態空間調度方法。針對分段建造的不同階段，在分析影響因素的影響形式基礎上提出了動態調整策略，包括定位延時策略、進度控制策略和吊運等待策略，調整分段建造過程以適應影響因素的作用。構建了船舶分段建造仿真模型，實現了分段建造在影響因素作用下動態空間調度的仿真。以實際數據為輸入進行仿真分析，結果表明，該方法制定的調度計劃與實際作業情況接近，且能夠為分段生產計劃優化調整提供指導。

船舶分段;空間調度;仿真;優化

0　引言

按照現代造船模式的要求,船舶建造以分段為單元,制定計劃并組織生產。調度計劃人員需要按照生產計劃制定分段調度計劃，即安排分段的開工時間和作業位置。制定分段調度計劃，就是在滿足調度約束條件下獲得最優的分段空間布局,這是一類資源受限的空間調度問題[1-2]。文獻[3-4]采用分段空間調度算法，實現了分段布局的優化，比較好地解決了空間調度問題。但是分段建造除受場地資源約束外,還受多種因素影響，分段生產難以嚴格按照生產計劃執行，這導致理想的調度計劃與現場作業差別很大，不能用于指導生產。

為了縮小調度計劃與現場作業情況之間的差別，有學者開始研究動態空間調度方法。Li等[5]提出了一種動態調度方法,采用預計劃算法對分段進行預調度,然后使用遺傳算法對分段進行空間排列。Li等[6]提出了虛擬生產系統的自適應動態調度算法,并通過分析動態事件的局部影響制定自適應措施。張志英等[7]考慮調度過程中存在的不確定因素,針對不同的分段影響事件提出了不同的調整和響應措施。趙明華等[8]針對曲面分段作業中出現的異常提出了自動調整算法,實現了分段作業計劃的調整。也有學者采用仿真技術分析生產系統不確定因素，或使用仿真預測的方式對調度計劃進行調整。朱琳等[9]建立了車間物流仿真模型獲取生產數據,用于物料擺放的布局優化,但是沒有考慮生產影響因素。劉建鋒等[10]根據國內船廠的生產實際,構造排序函數和分段布局規則,對船舶分段制造計劃的場地安排進行了模擬和優化,同樣沒有考慮分段建造影響因素。王岳等[11]建立了船舶平面分段仿真模型，對計劃執行情況進行仿真，并對計劃變動進行快速評估。Cha等[12]設計了離散事件仿真系統，模擬分段建造物料吊運過程生產中的不確定因素。張光發等[13]構造了船舶建造仿真系統,對船舶制造中的不確定因素進行模擬,實現了船舶建造計劃的仿真,但是并沒有針對分段布局進行優化。Liu等[14-15]提出了基于仿真的混合空間調度方法，實現了長期調度計劃的制定,但是仿真中考慮的不確定因素數量偏少，而且是采用平均分布來描述的,誤差較大。

上述研究主要從兩個方面展開：一是分析分段建造影響因素，研究動態空間調度調整策略，但調整是在突發事件已經發生的情況下進行的，并沒有考慮到生產計劃自身存在的問題。二是采用仿真技術模擬分段建造過程，獲取調度計劃或者實現對生產計劃的驗證，但是在仿真過程中不是缺乏考慮影響因素，就是缺乏分段布局調整。上述研究大多將空間調度和仿真割裂開來，沒有統一進行研究。

本文針對船舶分段空間調度和分段建造仿真中存在的問題，提出了基于仿真的船舶分段建造動態空間調度方法。在分析分段建造過程的基礎上考慮影響因素的作用，設計了對應的調整策略，形成動態空間調度；構造了船舶分段建造動態空間調度仿真模型，預測調度過程中影響因素所造成的影響，實現了分段建造動態空間調度仿真。采用實際數據進行仿真，輸出分段的動態布局、分段按時完工率、場地利用率等數據，通過對比其他方式獲取的數據，驗證了方法的可行性，同時指導了分段生產計劃的優化調整。

1　問題描述

1.1裝焊工場和分段數學描述

動態空間調度仿真框架如圖1所示。分段在裝焊工場中進行建造，裝焊工場由若干個跨組成，如圖2所示，每個跨上裝配有焊接、吊運設備等。建造完成的分段從安全通道中運走。

圖1　動態空間調度仿真框架

圖2　裝焊工場、跨、分段示意圖

裝焊工場的數學模型如下：

Jj:LjBjj=1,2,…,M

(1)

其中,Jj表示跨j,Lj、Bj分別表示跨j的長度和寬度,M表示跨的數量。

一旦分段在裝焊工場確定位置，那么直到分段建造完成，分段的位置都不能移動,其所占據的空間也不能被其他分段占據。分段在裝焊工場的占用區域為

Di={(xi,yi,Ji),Si,hi}i=1,2,…,N

(2)

其中,Di是分段i在裝焊工場的投影占據的區域;(xi,yi,Ji)是分段i的投影參考點坐標,參考點取分段左下點,如圖2中分段所示,Ji是分段i所在跨的編號,xi、yi表示參考點在跨Ji上的坐標;Si是分段i的形狀;hi是分段i的高度。

按照生產計劃，分段建造需要在其時間窗內完成，即在最早開工時間E和最晚完工時間F之間開工并完成。分段建造時間窗和分段開工時間T、建造周期P滿足下式：

(3)

1.2動態空間調度數學模型

動態空間調度數學模型如下：

(4)

(5)

(6)

(7)

(8)

如果分段空間調度時能夠考慮停工影響,準確預測分段完工時間Tf、移出時間Tm，那么分段調度計劃與現場作業的差別將大大縮小。此時的空間調度則需要依據分段建造過程、影響因素和分段高度等因素進行動態調整，是動態的空間調度。

1.3分段建造主要影響因素分析

要實現分段動態空間調度，首先要分析分段建造的影響因素。以上海某造船企業為例，對分段的主要影響因素進行統計，結果見表1。

表1　分段建造主要影響因素

設備因素主要考慮設備無法正常運行，導致分段建造過程受到影響。每個分段在建造中會使用到若干臺焊機，焊機故障會導致分段建造進度減緩。裝焊工場中，每個跨有若干臺吊運設備，吊運設備服務于跨間的不同區域。按照規程，吊運設備運行若干時間段后需要進行保養，保養期間，其所服務區域內的分段建造、吊運作業停止。

人員因素和氣候因素導致生產工作時間發生變化，使分段建造進度受到影響。假期期間，分段建造的一切工作將停止。加班是在標準工時的基礎上，增加工作時間。當最高氣溫達到法定高溫(36℃)時，將減少當天標準工時。

生產變動因素主要是分段的建造周期發生變化，導致分段完工時間發生變化。檢驗不合格分段需要進行若干天的修整，達到設計要求后，分段才算是建造完成。

2　船舶分段建造動態空間調度

分段建造按照不同的過程設計了不同的調度策略：待開工分段進行空間定位，如果處于停工階段或分段放置不下,則采用定位延遲策略；已定位分段進行建造，采用進度控制策略；完工分段進行吊運移出，如果處在停工階段、吊運設備保養階段或分段周圍存在高度干涉，則采用吊運等待策略。

2.1分段空間定位

分段空間定位就是采用空間調度算法,計算分段的最優布局。分段最優布局計算分為兩個步驟:首先是對開工的分段進行序列優化,采用遺傳算法[3]等智能算法;然后按照優化后的序列計算分段的最優位置,采用啟發式定位規則[4]計算分段二維位置。

空間定位時，只考慮假期因素造成停工，此時執行定位延遲策略，將分段定位延遲到下一個調度時間。沒有空間放置的分段，也執行定位推遲策略。分段空間定位的流程如圖3所示。

圖3　分段空間定位流程

2.2分段建造完工預測

分段建造采用進度控制策略，預測分段的完工時間Tf。建造進度與影響因素的影響形式有很大的關系，將主要影響因素的影響形式分為四種：一是停止分段建造活動，如吊運設備保養、假期；二是直接減緩分段建造進度，如焊機故障；三是改變工作時間，從而間接改變分段建造進度，如加班、高溫；四是直接增加分段的建造周期，如完工檢驗不合格。

分段的建造過程主要是將零部件吊運到指定位置,然后采用焊接設備將零部件焊裝在一起。以該主要過程為基礎,為便于分析，默認分段不在受影響因素作用下每天建造進度是相同的。針對前三種影響因素，設計分段的建造進度預測模型：分段以1天為單位進行建造進度預測，分段i在t天的建造進度是前t-1天進度與t天新增進度之和：

Pro(Di,t)=Pro(Di,t-1)+

(9)

i=1,2,…,N

其中,Xi(t)是分段建造活動狀態,由吊運設備保養和假期共同控制,Xi(t)=0或1;Y是焊接設備總數,Yi(t)是正常工作的焊機設備數量;Z是標準工時,Zi(t)是實際生產時間，主要由加班和高溫因素控制;Wi是分段每天標準建造進度，滿足WiPi=1。

當Pro(Di,t)=1時,考慮第四種影響形式。對分段進行合格檢驗，檢驗不合格的分段將要進行mi天的修整,使得分段達到合格，合格的分段才是建造完工的分段。

2.3完工分段吊運移出

完工分段移出采取吊運等待策略，來獲得移出時間Tm。當處在吊運設備保養、假期等階段時，吊運活動停止，此時執行吊運等待策略，等待下一個調度時刻。完工的分段使用吊運設備將其吊運出去,當分段周圍存在過高的分段，阻擋分段吊運時，同樣執行調度等待策略。

如圖4所示，分段112周圍有分段，吊運時需要判斷是否存在高度干涉。假設最大吊運高度是Hm，待吊運分段的高度是H，分段之間的安全距離是Hs,待吊運分段在Y軸兩側移出方向上其他分段的最高位置分別是H1、H2。如果分段能夠從跨中吊運出去，則存在i=1或2，滿足：

H+Hi+Hs≤Hm

(10)

圖4　分段吊運仿真示意圖

對于不能調運的分段,將其一直放置在原地,直到能夠滿足式(10),過程就是執行吊運等待策略。在建造過程中，分段的高度是依據分段的建造進度不斷變化的，需要實時更新分段的高度。

3　船舶分段建造仿真模型

船舶分段建造的不同過程可以看成若干個離散的事件,采用離散事件系統仿真技術，構建船舶分段建造仿真模型，實現分段建造的動態空間調度仿真。

3.1仿真模型架構設計

采用面向對象的方法構造仿真模型，模型對象如圖5所示。

圖5　仿真模型對象

仿真模型共有兩組對象：仿真引擎對象和動態空間調度對象。仿真引擎對象是離散事件系統仿真模型中必不可少的：仿真控制器是模型的核心，其主要功能是控制仿真流程，使得仿真朝著預定的流程執行；統計計數器用來統計仿真過程中數據；隨機數發生器生成隨機數，通過數學變換生成其他的隨機分布；仿真時鐘控制仿真時鐘的推進。動態空間調度對象是仿真中主要的執行體：調度執行對象的作用是生成事件列表，并針對不同建造過程對象處理不同的事件；調度事件列表記錄調度時刻的分段及其類型，包括開工的分段、建造的分段和完工的分段；建造過程對象是用來處理不同類型分段的方法，包括空間定位對象、分段建造對象和吊運移出對象；影響因素對象的作用是獲取主要影響因素的狀態數據(例如是否加班、損壞焊機維修時間等)，實現流程如圖6所示。

圖6　影響因素狀態數據獲取流程

使用封裝技術將對象中的功能封裝成類。采用繼承多態的方式，實現分段建造影響因素對象和三種建造對象的功能及其調整策略。仿真模型的UML類圖如圖7所示，通過構造這些類來實現仿真模型。

圖7　仿真模型的UML類圖

3.2仿真模型實現流程

在仿真控制器Simulator控制下，仿真模型執行流程如圖8所示。

仿真開始前,輸入仿真信息，包括裝焊工場跨的數量、尺寸,分段的尺寸和生產計劃，主要影響因素數據。然后對仿真主控進行初始化，對影響因素進行建模。

圖8　仿真系統模時序圖

仿真時，調度執行類依據仿真時間，生成事件列表；對開工的分段進行空間定位，位置計算成功的分段和已定位的分段進行建造進度預測；對完工的分段進行吊運移出操作。將仿真的結果反饋到統計分析類,然后設置下一個仿真時刻，進入下一輪仿真。

仿真結束后，輸出分段的建造情況、場地的利用情況和分段動態布局。

4　案例應用與分析

以VS2010 MFC軟件作為編程工具，開發一套船舶分段建造動態調度仿真系統。輸入分段建造的影響因素、生產計劃，輸出分段生產評價指標，動態布局。

4.1主要影響因素統計數據

以上海某船舶企業作業區間歷史數據和2014年高溫出現概率預測數據(參考2010～2013年上海氣溫),統計分析得出分段建造主要影響因素的數據和設備配置情況，結果見表2。

4.2案例仿真驗證

分段建造計劃選取該船廠生產的7.6萬噸散貨船。建造數量是4，每條船有150個分段，部分分段建造生產計劃見表3,表3中,P、h分別表示分段周期和高度。裝焊工場有3個跨,跨的長度都是275 m,寬度都是25 m。每個跨上有6臺吊運設備,最大吊運高度是20 m。為便于分析，分段高度按照建造進度線性變化。

表2　主要影響因素統計數據

說明：表中略去吊運設備的初次保養時間；形如x-y表示日期，例如7-1表示7月1日，日期均為2014年。

表3　分段(部分)建造生產計劃(日期均為2014年)

利用原型系統,對分段建造進行10次仿真。由于調度計劃難以實施,現場作業時分段是沿著裝焊工場安全通道的方向進行一維空間布局的,對這樣的布局方式同樣進行10次仿真。兩種情況均仿真后，統計分段完工情況，其結果見表4。分段移出時間Tm如果不遲于最晚完工時間F(Tm≤F),此時分段就算按時完工。

將實際作業、空間調度計算的結果和上述兩種仿真進行對比,見表5,其中延遲開工指分段開工時間T大于最早開工時間E,即T>E。通常,船舶企業的實際按時完工率約75%,實際作業調度方式仿真后的按時完工率是78.1%,與實際作業基本相符。而采用本文方法后,減小了延期開工分段數，提高了場地利用率，使按時完工率提高3.5%,達到81.6%;雖然仿真一次的時間從2.1 min延長到20.5 min,主要是因為采用了布局優化算法,耗時比較多,但是在時間上的損失是值得的?？臻g調度算法和本文方法耗時相差不多,主要是分段布局優化耗時比較長，在此算法中分段基本上是按照生產計劃來生產的,統計按時完工率沒有意義。仿真結果表明,本文方法能夠縮小調度計劃與實際作業之間的差別,同時能夠提高場地利用率。采用本文方法仿真輸出的布局如圖9所示,可作為分段調度計劃。

表4　分段按時完工情況統計

表5　仿真結果與實際調度對比

圖9　分段布局動態界面(2014-1-31部分布局)(日期均為2014年)

圖10對裝焊工場利用率進行了統計。圖10中,利用率出現了4處峰值和3處低谷,而且第三個跨的利用率偏低，這說明單條船的分段建造計劃相對集中，而多條船之間的集中建造時間間隔比較大，裝焊工場利用不充分。如果適當縮小多條船的集中建造時間間隔，在保證按時完工率的基礎上，可以提高裝焊工場的利用率。

分析圖10中波峰之間的時間間隔和波峰之間的利用率變化情況，預測船號H2471、H2472、H2473的建造時間可以分別提前10 d、20 d、30 d。按照預測優化調整后的生產計劃，仿真10次分段建造。統計分段按時完工率達到81.3%，與優化前基本保持一致。圖11是裝焊工場場地利用率統計圖，與圖10相比，利用率曲線明顯平緩，利用率得到了大幅度的提高。可見,利用本文方法能夠有效地評估分段生產計劃、同時指導生產計劃的優化調整。

圖10　裝焊工場場地利用率(日期均為2014年)

圖11　生產計劃調整后場地利用率(日期均為2014年)

5　結語

本文針對船舶分段建造空間調度過程中存在的問題,在分析分段動態空間調度數學模型和分段建造的主要影響因素的基礎上，設計了分段建造動態空間調度調整策略，使得分段建造過程能夠按照影響因素的作用進行動態調整。采用離散事件仿真技術，建立了船舶分段動態空間調度仿真模型，實現了分段建造動態空間調度的仿真，并開發了原型系統。采用實際數據作為輸入進行仿真，結果表明,本文方法使調度計劃更好地反映實際作業情況，并且提高了場地利用率；仿真輸出的布局可以作為調度計劃來指導現場作業；仿真結果可為生產計劃評估、優化調整提供指導。但本文提出的動態空間調度策略中分段進度預測模型是理想化的,分段高度變化是取線性變化的，今后將考慮實際變化情況對其進行改進。

[1]Lee K J,Lee J K,Choi S Y.A Spatial Scheduling System and Its Application to Shipbuilding:DAS-CURVE[J].Expert Systems with Applications,1996,10(3):311-324.

[2]Lee J K,Lee K J,Park H K,et al.Developing Scheduling Systems for Daewoo Shipbuilding: DAS Project[J].European Journal of Operational Research,1997,97(2):380-395.

[3]馬少輝,王景秋,陸春霞,等.動態空間調度的混合遺傳算法[J].運籌與管理,2013,22(2):99-104.

Ma Shaohui,Wang Jingqiu,Lu Chunxia.et al.A Dynamic Spatial Scheduling Approach Based on Hybrid Genetic Algorithm[J].Operations Research and Management Science,2013,22(2):99-104.

[4]Koh S,Eom C,Jang J,et al.An Improved Spatial Scheduling Algorithm for Block Assembly Shop in Shipbuilding Company[C]//The 3rd International Conference on Innovative Computing Information and Control.Dalian:IEEE, 2008:253-256.

[5]Li Bo,Zhao Zhiyan,Li Gang.A Dynamic Scheduling Method for Spatial Layout Planning[C]//Proceedings of the 4th International Conference on Machine Learning and Cybernetics.Guangzhou:IEEE,2005:18-21.

[6]Li Lin,Jiang Zhibin.Self-adaptive Dynamic Scheduling of Virtual Production Systems[J].International Journal of Production Research,2007,45(9):1937-1951.

[7]張志英,徐晨,毛祖杰,等.基于規則的船舶分段動態空間調度方法[J].上海交通大學學報,2010,44(8):1019-1025.

Zhang Zhiying,Xu Cheng,Mao Zhujie,et al.Rule Based Dynamic Spatial Scheduling for Hull Block Construction[J].Journal of Shanghai Jiaotong University,2010,44(8):1019-1025.

[8]趙明華,蔣祖華.針對異常的船舶曲面分段作業計劃自動調整算法[J].上海交通大學學報, 2010, 44(3):428-432.

Zhao Minghua,Jiang Zhuhua.Algorithm of Automatic Adjustment in Curved Blocks Building Schedule Subject to Exceptions[J].Journal of Shanghai Jiaotong University,2010,44(3):428-432.

[9]朱琳,何其昌,范秀敏.多品種混合裝配車間配料區物料擺放布局優化[J].中國機械工程,2012, 23(22):2708-2713.

Zhu Lin,He Qichang,Fan Xiumin.Optimization of Warehouse Items Layout In a Mixed Assembly Workshop[J].China Mechanical Engineering,2012,23(22):2708-2713.

[10]劉建峰,秦士元,應長春.船舶分段制造日程計劃的模擬與優化[J].中國造船,2000, 41(4):13-21.

Liu Jianfeng,Qin Shiyuan,Ying Changchun.Block Construction Scheduling Simulating and Optimizing[J].Ship Building of China,2000,41(4):13-21.

[11]王岳,姚偉,蔣志勇.基于虛擬仿真的船舶平面分段生產計劃調整技術研究[J].中國造船,2012,53(3):192-198.

Wang Yue,Yao Wei,Jiang Zhiyong.Simulation-Based Research on Adjustment Technology of Production Plan on Plane Assembly Lines with Blocked Jobs[J].Ship Building of China,2012,53(3):192-198.

[12]Cha J H,Roh M.Combined Discrete Event and Discrete Time Simulation Framework and Its Application to the Block Erection Process in Shipbuilding[J].Advances in Engineering Software,2010,41:656-665.

[13]張光發,劉玉君,紀卓尚.船舶分段建造計劃仿真與優化[J].計算機集成制造系統, 2011,17(12):2643-2651.

Zhang Guangfa,Liu Yujun,Ji Zhuoshang.Simulation and Optimization of Ship Block-Building Planning[J].Computer Integrated Manufacturing Systems,2011,17(12)：2643-2651.

[14]Liu Z,Huat D C K,Wee K H.Scheduling Dynamic Block Assembly in Shipbuilding through Hybrid Simulation and Spatial Optimization[J].International Journal of Production Research,2012,50(20):5986-6004.

[15]Liu Z,Chua D K,Wee K H.A Simulation Model for Spatial Scheduling Dynamic Block Assembly in Shipbuilding[J].Journal of Engineering, Project and Production Management,2011,1(1):3-12.

(編輯陳勇)

Simulation-based Ship Block Building Dynamic Spatial Scheduling

Wang Jinjian1Du Jiwang1Fan Xiumin1,2He Qichang1,2

1.Shanghai Jiaotong University,Shanghai,200240 2.Shanghai Key Lab of Advanced Manufacturing Environment,Shanghai,200240

To reduce the difference among ship block spatial scheduling results and actual working assignments,a simulation-based dynamic spatial scheduling method was proposed.According to different stages of ship-block building and analyzing the influence forms of affecting factors,three dynamic adjustment strategies were put forward,including positioning delay strategy,progress control strategy and swing waiting strategy.With these strategies,the ship-block building processes could be adjusted so as to adapt to affecting factors.A ship block building simulation model was developed to realize the dynamic spatial scheduling simulation under the influence of affecting factors.The simulation results indicate that the proposed method can reduce the difference between the scheduling plan and actual working ones,and can provide guidance to optimize ship-block building production plan.

ship block;dynamic spatial scheduling;simulation;optimization

2014-09-28

國防基礎科研項目(A0720133009)

TP391.9DOI：10.3969/j.issn.1004-132X.2015.14.011

王津劍,男,1989年生。上海交通大學機械與動力工程學院碩士研究生。主要研究方向為生產系統建模仿真與仿真。杜吉旺,男,1987年生。上海交通大學機械與動力工程學院博士研究生。范秀敏,女,1971年生。上海交通大學機械與動力工程學院教授、博士研究生導師。何其昌,男,1977年生。上海交通大學機械與動力工程學院講師。