基于仿真的船舶分段建造动态空间调度

王津剑　杜吉旺　范秀敏,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,主要是因为采用了布局优化算法,耗时比较多,但是在时间上的损失是值得的。空间调度算法和本文方法耗时相差不多,主要是分段布局优化耗时比较长，在此算法中分段基本上是按照生产计划来生产的,统计按时完工率没有意义。仿真结果表明,本文方法能够缩小调度计划与实际作业之间的差别,同时能够提高场地利用率。采用本文方法仿真输出的布局如图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年生。上海交通大学机械与动力工程学院讲师。