分段堆场的动态调度方法

2017-03-06孙晓军董飞梁凤婷董贵颖

计算机时代 2017年2期

孙晓军++董飞+梁凤婷+董贵颖

摘要：针对造船过程中分段堆场的堆放混乱和调度效率低下的问题，通过紧密结合调度规则，以使分段移动过程中产生的衍生指令数最小为目标，综合考虑分段的时间和空间要求，兼顾相关场地堆放不合理分段的调整，提出目标分段移入场地的位置选择和出入堆场路径优化的方法，并设计了计算流程。在场地堆放率为83.6%的情况下经过多次实验，得到的衍生指令的平均比例降低到37.89%，得到了良好的调度结果，证明该方法在分段调度问题上的有效性。

关键词：船体分段；生产调度；衍生指令；动态调整；路径规划

中图分类号：U673 文献标志码：A 文章编号：1006-8228（2017）02-60-05

0 引言

在现代造船模式下，船体分段制造活动是整个造船过程的瓶颈，其生产周期长，生产过程中的资源约束多。在分段制造過程中，分段堆场往往出现密集堆放的情况，并且生产计划时常变动。这难免会导致分段堆场的堵塞现象的发生，使得分段调度效率低下，造成制船厂额外的运输成本。

目前对分段堆场的调度研究较多，张志英等针对矩形分段提出了一种基于改进粒子群算法的动态空间调度方法，利用改进粒子群算法对分段进行加工排序，在算法设计时采用遗传算法与粒子群算法的部分结合，通过自适应惯性权重策略实现了算法的收敛性[1]。陶宁蓉等针对船体各种不规则分段，提出将空间资源作为关键资源的空间调度问题，以具有时间窗约束的空间调度三维模型为基础，提出了结合禁忌搜索和基于极点的定位规则的优化算法[2]。郑俊丽等针对船体分段制造提出具体的模型及解决方法，主要利用三维装箱问题来解决，最后通过一个系统的实现具体的显示了所写算法的正确性及可行性[3]。谢甜就分段堆场堆放混乱、分段难查询等问题，综合分析各部门分段建造及船舶合拢的一般规律，提出了分段调度和场地规划方案[4]。马少辉等针对矩形分段基于遗传算法安排加工顺序、利用平均最大矩形启发策略安排空间位置[5]。张志英等考虑船舶分段堆场调度过程中的扰动因素，结合分段的质量和移动距离建立数学模型，并用改进遗传算法提出分段在堆场中堆放位置的较优方案[6]。

本文以分段移动过程中产生的衍生指令数最小为目标，考虑场地属性和分段要求匹配，兼顾分段的剩余加工周期天数和所占场地的阻力系数进行动态调整，难点就在于动态调整的过程，最终提出船体分段调度的算法。这一算法使得调度问题的计算过程更加透明，通过计算可得到具体的调度指令，使调度有序的进行，可操作性更强。

1 问题分析

在现代造船模式下，在船体装配之前，船体分段需要先后在多个堆场中进行堆放以及加工，如舾晒、喷砂、涂装、打磨和小装配等。每个堆场容量有限并且功能相对单一，而每个分段所要求进行的工艺阶段是不同的，这就要求各个分段在几个堆场之间进行不同而有序的单向流动。

场地按照空间位置即工艺不同划分成为多个隔离的二级场地，而每一个小方格是容纳分段的三级场地。每天，业务部门都会向物流部门提出若干分段移动的需求，由于目标分段存放在各二级场地上，而二级场地上没有预留平板车行驶的空间，平板车移出目标分段就需要先挪开路径上的其他分段，即衍生指令，使得分段调度问题复杂化，加大了调度工作量，这就导致了分段堆场的调度问题的出现。

2 调度指令的优化策略

为了方便问题的研究可以做出如下假设：

⑴ 每个三级场地只放一个分段；

⑵ 分段的重量对于搬运工作没有影响；

⑶ 由于衍生指令而移动的分段在工作指令完成之后不需要搬运回原位置。

2.1 符号设置

为了简化描述，采用下述符号表示：

i：某三级场地在对应的二级场地中的行序号；

j：某三级场地在对应的二级场地中的列序号；

：工艺n二级场地上的三级场地（i，j）的分段；

：工艺n二级场地上的三级场地（i，j）；

：工艺n二级场地上的三级场地（i，j）的堆放系数；

：位于工艺n级场地上的三级场地（i，j）的分段的阻力值；

：位于工艺n级场地上的三级场地（i，j）的分段在工艺m二级场地上的工艺周期天数。

2.2 船体分段调度规则

⑴ 移动申请清单排序

一个完整的移动申请清单包括以下几个部分：移动申请ID、移动分段ID、移出区域（三级场地）、移入区域（二级场地）、工艺流向、动能需求、分段在该场地的工艺周期天数。

对于有移动需求的若干分段，按分段提取的优先级进行排序，加工工艺流向靠后的或者工艺周期短的靠前，相反则靠后。要求工艺流向靠后的分段首先被执行，因为其工艺更接近装配环节，其移出后留下的空位可以为前序工艺的分段使用，从而减少衍生指令的产生。

⑵ 计算空闲场地

在分段的移动流程开始前，要先确定二级场地中空闲着的三级场地，它包括已经存在的空闲三级场地，以及分段将要移出的三级场地。

⑶ 计算场地阻力

场地阻力值指的是平板车经过某个三级场地所遇到的阻力，空场地的阻力值为0，有分段摆放的三级场地阻力值为某一具体值。

从整体优化的角度来看，在分段移动过程中应协调场地的堆放系数与分段工艺周期的关系，调整相关堆场里堆放不合理的情况。工艺周期天数较大的分段近期提取的可能性较小，应放置在堆放系数较大的三级场地以免阻挡其他分段的提取，而工艺周期天数较小的分段应放置在堆放系数较小的三级场地以便于进出。首先确定该二级场地的堆放系数数列，如图1所示。其次按照分段在该场地的剩余工艺周期天数进行排序。最后将分段的剩余周期天数和堆放系数做对比，判断分段堆放是否合理。若分段堆放合理，设置其阻力值为1；若某分段的剩余周期天数排序靠前（周期较长）而堆放系数很小，即堆放不合理，则将其阻力值设为a（a<1），a<1表示若产生衍生指令则优先移动堆放不合理的分段。

⑷ 获取最短路径

为使进出场过程中衍生指令最少，利用dijkstra方法比对每个三级场地的所有出场路径。将每个二级场地构建成一个网络，构建方法如下：以每个三级场地为顶点，相邻的两个三级场地之间用有向边连接，权重为进入该场地的阻力值，构建场地有向图。利用路径计算方法，可以计算出每个三级场地至道路阻力值最小的路径。

⑸ 移入指定三级场地

移入指定三级场地实际上包括两个步骤：选定目标三级场地和决定最优的进入路径。在选定目标三级场地时要注意所选三级场地应符合各项约束条件，包括硬性约束和软性约束。硬性约束包括满足动能源、工艺流向、大分段摆放，软性约束包括场地优先级、场地堆放系数等。硬性约束必须满足，软性约束包括满足场地堆放系数与分段工艺周期的匹配等。

获取分段的入场路径与出场路径相似，不同点在于入场时要计算的是各空闲三级场地的最短路径值。

⑹ 平板运输指令运算以及分发

平板运输指令运算，要按照先后顺序进行待移入场地盘整、待移出场地盘整、计划指令。并规定，衍生指令产生的分段优先放置于空闲位置，如果没有空闲位置则放回原位；前后有重复的衍生指令需要合并，优化指令体系，避免各条指令中的冲突问题。

2.3 船体分段调度流程图

根据分段堆场的调度规则做出实际分段堆场的调度流程图，如图2所示。

[开始][输入分段移动申请][更新移动申请清单][根据工艺流向/周期进行移动清单排序][找到移出场地的

不匹配分段][计算分段的移出路径][排除该路径][最优路径？] [更新移出堆场的堆放情况] [否][是][结束][生成平板车运输

指令并下达][处理完所有申请？] [更新平板车运输指令清单][更新移入堆场堆放情况][最优位置的最优路径？] [排除该路径][计算分段的移入路径][最优位置？] [排除该位置][选择分段的移入位置][计算移入场地的阻力值][找到移入场地的

最短移入路径：

衍生指令：

⑹ 更新移动指令清单，当前只需移动分段001，需重新计算阻力值。如图8所示，在分段012的移动过程中将原分段移到了三级堆场上，实现了三级场地的相对优化。

3.2 仿真实验验证

最后我们利用仿真程序，通过对10个不同场地摆放的模拟，在堆场堆放率达到83.6%的情况下进行了20次试调度，对其结果进行分析可以得到衍生指令占总指令比例的平均值为37.89%，低于40%。从这一仿真结果来看，本文给出的调度策略，可以在堆场堆存率达到80%的情况下，将衍生指令降低到占总指令的40%以下，达到了整体优化的目标，有效减了因衍生指令而产生的运力、时间等成本。

4 结论

本文提出的分段调度方法能有效改善造船厂分段堆场堆放不合理的情况，通过综合考虑分段的工艺流向、工艺周期，结合移出堆场和移入堆场的阻力系数分布，兼顾不合理分段的调整。降低了调度任务中移动次数，提高了堆场的物流效率，更加有利于造船厂对分段堆场进行管理。但在现实生活中，一个三级场地可以不止堆放一个分段，未来可对一个三级场地堆放若干分段的复杂问题进行进一步的研究。

参考文献（Reference）：

[1] 张志英.改进粒子群算法的动态空间调度方法[J].哈尔滨工

程大学学报，2009.30（12）：1344-1350

[2] 陶宁蓉.带时间窗约束的船体分段空间调度问题[J].计算机

集成制造系统，2010.16（12）：2674-2679

[3] 鄭俊丽.船舶分段制造车间的模块空间调度模型及算法[D].

上海交通大学硕士学位论文，2011.

[4] 谢甜.分段调度优化与堆场规划研究[J].上海船舶运输科学

研究所学报，2012.35（21）：81-84

[5] 马少辉.动态空间调度的混合遗传算法[J].运筹与管理，

2013.22（2）：99-104

[6] 张志英，计峰，曾建智.基于改进GA的分段堆场计划调度方