分段堆场预测调度研究

周 健，曹瑞霞，汪 雄

同济大学 机械工程学院 工业工程系，上海 201804

分段堆场预测调度研究

周 健，曹瑞霞，汪 雄

同济大学 机械工程学院 工业工程系，上海 201804

1 引言

船舶分段堆场是船企不可或缺的重要资源，是分段脱胎后进行后处理的堆放或暂存的场所。由于受一些因素的影响，比如天气、设备、船东检验等，分段脱胎后与后续工序之间的周转流动并非“即时无缝”连接，导致脱胎的分段不能及时送往船坞搭载，造成大量的库存积压、道路堵塞、各种潜在的质量问题等，从而大大增加了对堆场资源的需求，同时，人为预测的进出场段数并没有考虑这些因素的影响，也导致了实际执行的调度计划与所排计划偏差较大。实际上，堆场不堪负荷，已成为限制船厂物流系统正常运转的瓶颈。另外，由于不合理的调度机制和缺乏有效的管理信息系统，分段处于无序堆放状态，给生产管理带来很多问题。因此，对船舶分段堆场的调度进行研究并通过预测制定合理的堆场调度计划已迫在眉睫。

面向船舶制造的分段堆场调度属于二维空间平面调度问题，但此类问题类似于集装箱堆场调度问题。针对集装箱的翻箱量问题，有学者通过建立最小生成树模型，并运用动态规划方法和启发式算法求解模型确定最小翻箱量[1-5]。文献[6]考虑集装箱码放顺序的全序关系，设计单箱码放算法求解动态码放模型。文献[7]以最小化翻箱率为目标，建立两阶段优化模型，研究集中到达和分散到达两种进场模式下的优化效果，并进行仿真模拟。文献[8]运用启发式算法讨论了考虑集装箱重量等级的翻箱量最小化问题。文献[9]建立考虑集装箱重量的出口箱区堆存模型并利用搜索技术求解该模型。文献[10]以图搜索和模式识别技术为基础建立了出口箱混合顺序作业堆场贝优化模型。集装箱堆场调度中箱位分配和翻箱量类似于船舶堆场中的分段停放位置和临时移动分段数量，但两者的堆放规则不同，前者属于分层堆放，而后者是平面堆放。目前国内外专门针对这类问题的研究较少，Changkyu等以临时分段移动量最少为目标建立优化模型，提出遗传算法和改进动态启发式算法对模型进行求解[11-12]。蒋祖华等通过设定特定的调度规则，并运用启发式调度算法求解堆场调度模型[13]。然而这些方法都是在假定堆场场地固化（场地上用于腾空摆放分段的设施缺乏柔性）的生产环境中进行，从而限定分段在堆场中的移动路径，导致分段必须笔直地进出堆场，大大增加了临时分段移动量。针对预测调度问题，文献[14]对不确定环境下的Job Shop调度，分析生产干扰及其扩散效应的随机性特征，提出了一种基于设备整体效能（OEE）的具有鲁棒性的预测调度实现方法。文献[15]研究基于一定概率分布对机器故障的预测描述，利用插入时间冗余的预测调度方法使初始调度方案具有一定的抗干扰能力，使未来实现调度与预测调度尽量保持一致性。

本文用BP神经网络对未来一个周期内的进出场段数进行预测，并以分段移动度最小为优化目标，运用分支定界法和启发式规则对分段在堆场中的调度问题进行建模。合理安排分段进出堆场顺序，确定分段在堆场中的最优停放位置，规划其进、出堆场的移动路径，从而优化堆场资源的利用率，提高堆场周转率。并结合某船厂实际数据对模型进行了实例验证。

2 问题描述与解决方法

2.1 问题描述

由于受到一些外在因素的影响，实际进出场段数与理论段数之间存在偏差，必将导致调度计划的执行力减弱。因此提前对未来一个周期内的进出场段数进行预测显得十分必要。

分段按其在堆场中的作业类型可分为进场分段、出场分段。进场分段是脱胎后，要移进堆场进行后续处理或暂存的分段；出场分段是指在堆场中完成了后续处理或暂存，运往船坞搭载等后续工位的分段。临时分段是指对分段进入或移出堆场过程造成阻碍的分段。在调度过程中需要先将临时分段移至道路或临时场地上，等计划分段到达目的位置后，再将其移回原处。分段移动度指平板车在堆场中搬运进、出场分段到目的地整个过程的移动难度。在搬运过程中，若平板车遇到1个临时分段，则移动度增加α。为了区别相同临时移动分段数的路径而定义系数 β，β是指平板车经过1个场地的移动难度。由于平板车搬运一个分段的成本远高于经过一个场地的成本。因此，α≫β，本文取α=1，β=0.000 1。分段进、出堆场的移动路径并不唯一，不同的移动路径具有不等的分段移动度。

考虑到分段堆场的实际情况及便于堆场调度问题的研究，假设为：（1）分段按计划时间进、出堆场，不存在提前、延期和占先；（2）分段进出堆场的道路确定且唯一；（3）堆场由若干大小相等的正方形场地组成；（4）分段用最小包络矩形近似；（5）一个作业场地只能放一个分段；（6）各装卸设备正常运行；（7）临时分段只能移动到道路或与其相邻的四个临时场地上，而且完成分段移动后，临时分段须移回原处。要解决的问题有：（1）确定进场分段在堆场中合适的停放位置；（2）确定分段进出堆场的最佳移动路径。船舶分段堆场调度如图1所示。

图1 船舶分段堆场调度示意图

2.2 解决方法

本文以船厂过去半年的实际进出场段数为样本，综合考虑天气情况、设备好坏、船东检验与否等实际因素，对未来一个周期内的进出场段数做出预测。同时以分段移动度最小建立目标函数。对于调度周期内的进场分段，首先结合优化目标，利用分支定界法为其安排停放位置，然后规划其在堆场中的移动路径。对于出场分段，则只需根据其在堆场中的停放位置规划出场路径即可。确定分段的移动路径需经过两个步骤：（1）根据启发式规则求出具有最少临时分段数的路径（可能不唯一）。（2）利用临时场地比较这些可行路径，具有最小分段移动度的为最优路径。分段堆场调度流程如图2所示。

图2 分段堆场调度流程图

3 建立分段堆场调度模型

3.1 神经网络预测模型

步骤如下：

步骤1训练样本的确定与处理

为监控训练过程，使之不发生“过拟合”和评价建立的网络模型的性能和泛化能力，把样本集按70%、15%、15%的比例分为训练样本、验证样本和检验样本。

另外，由于神经网络的多数学习算法不能适应很宽的数据变化范围，因此需要对样本进行归一化处理。

步骤2神经网络的输入输出

通过对影响进出场段数的因素分析，本文选取天气、设备、船东检验这3个因素作为神经网络的输入，日进出场段数作为输出，即神经网络的输入层拥有3个节点，其输出层拥有1个节点。

步骤3隐含层及隐含层节点数的确定

现有理论证明一个三层BP神经网络能以任意精度逼近任何非线性函数，故本文选用一个三层BP模型用于预测。隐含层节点数的确定是神经网络设计中非常重要的一环，隐含层节点数往往根据经验设计所得经验和自己进行实验来确定。本文通过神经网络训练来确定隐含层的节点数：首先根据经验公式（1）确定隐含层节点数目的范围，设计一个隐含层神经元数目可变的BP网络，通过三种样本误差和相关系数的对比，确定最佳的隐含层节点个数。

其中，n1为隐含层节点数目，n为输入层节点数目，m为输出层节点数目，a为0～10之间的任意常数。

步骤4训练函数及训练参数的确定

由于Levenberg-Marquardt算法具有收敛速度快，所占内存小和训练结果好的优点，本文选用训练函数trainlm；系统学习过程的稳定性受学习率的影响，为保证学习过程的收敛性，本文选取较小的学习率；由于在神经网络模型训练过程中，对有限的样本进行反复训练可能会造成网络的过拟合现象，因此在实际模型训练中采用设定最大迭代次数和训练目标来避免。

步骤5训练网络，构建面向船厂进出场段数的预测模型。

3.2 建立堆场状态矩阵

为了表示分段在堆场中的停放位置以及堆场中场地的状态，建立如图3所示的堆场状态矩阵。堆场状态矩阵是一个0-1矩阵，1表示场地上停放着一个且仅有一个分段，0表示场地上没有分段。图3表示一个5行9列的堆场，将位于第m行，第n列的作业场地命名为(m，n，h)，其中h是状态值，若该场地放有分段则其h为1，否则为0。

图3 堆场状态矩阵

3.3 堆场节点状态模型

为了求得分段移动路径上的临时分段数，将堆场中的作业场地和道路用节点表示，建立分段堆场节点状态模型。堆场中作业场地(m，n，h)表示对应的节点。道路用一个名为V0的节点表示，其状态始终为0。每个节点有上下左右四个方向，路径必然经过节点的其中两个方向。若节点状态为1，则其四个方向的路权为0.5，否则为0。因此，在分段进出堆场的路径上，每经过一个状态为1的节点，分段起始位置节点与目标位置节点间的距离就增加1。据此定义，节点间的距离如图4（a）所示。图4（b）表示相连节点的状态模型，即将相邻节点之间的路权相加。其中将两个状态为0的节点之间的距离定为0.001是为了区别不同的0节点。根据以上规则，可以将任意堆场转换为节点状态模型。由此，分段进、出堆场时，依照某路径从起始位置到达目标位置过程中需经过的临时分段数，可通过计算节点状态模型中对应路径上分段起始位置节点与目标位置节点间的距离，并将其数值取整数后得到。

图4 节点间的距离图

3.4 场地更新机制

作业场地的状态随分段进出堆场发生变化。若安排一个进场分段，则对应的停放场地的状态将由0变为1，若是出场分段从堆场中出来，则放置该分段的场地状态由1变为0。临时移动的分段因为其移出堆场后又需重新放回原位置，故其状态不变。

3.5 分段堆场调度模型

堆场作业计划以分段移动度最小为优化目标，对于出场分段，可以将道路看作起始点（即当作已确定位置的进场分段处理），从道路处开始寻最优路径来简化模型。参数设定如下：

A=(A1，A2，…，Ai，…，An)为T周期内待调度计划分段集，i=1，2，…，n；

(L，W)：堆场的尺寸；

(Li，Wi)：分段Ai的投影参数；

Ri=(ri1，ri2，…，rij，…，rim)为分段 Ai的具有最少临时分段数的路径集，j=1，2，…，m；

dij：路径rij经过的场地数量；

Grij=(grij1，grij2，…，grijk，…，grijz)为 rij对应的临时移动分段集，k=1，2，…，z；

hrijk：临时分段grijk需经过的场地数；

t0：T周期的开始时间；

tT：T周期的结束时间；

ti：Ai出场时间；

S0：单个作业场地的面积；

tijk：grijk的在场时间，其中临时分段的在场时间指该分段停留在堆场中所对应的时间；临时分段grijk本有四个相连场地（上，下，左，右），rij经过了其中两个场地，定义另外两个场地为(O1，O2)，称为临时场地，其中位于堆场边上的分段的临时场地集为（O1）或空集；

Wi：分段Ai开始调度时，堆场状态矩阵中“0”的个数；

(xv，yv)：T周期内在场分段Sv在堆场中的停放位置（xv，yv分别为堆场的行与列）；

i，j，v，a，b，d均为整数；

定义决策变量如下：

在堆场节点状态模型中，根据启发式规则求出的分段可行路径并不唯一。通过引入临时场地用于停放临时分段，本文根据目标函数（2）逐个计算并确定每个分段的可行路径集中具有最小分段移动度的路径，并得出该方案产生的最小总移动难度。然后运用遗传操作在所有方案中选出总移动度最小的方案来安排堆场计划；约束条件（3）限制分段的出场时间要在T周期内；约束条件（4）保证分段Ai出场时，需移动的临时分段的在场时间要晚于分段的计划开始时间；约束条件（5）表示作业场地能容下放置的分段；约束条件（6）到（9）限定一个作业场地只能放一个分段；约束条件（10）说明相邻的调度分段之间的堆场状态必定不同。

4 模型求解

船舶堆场调度模型求解如下：

（1）应用BP神经网络预测T周期内进出场段数。

（2）根据堆场状态矩阵建立堆场节点状态模型。

其中后阶段节点Vij与前阶段节点Vmn为相连节点，d(Vij，Vmn)表示两节点间的距离。运行过程中将所得节点的属性值放入open表中，把已完成搜索的节点的属性值放入close表中，删除open表中属性值已大于close表属性值的节点，若有新完成搜索的节点的属性值小于close的值，则替代原先的属性值。

图5 阶段分解方法

（4）分别记录这些路径所需经过的临时分段以及这些分段的相邻场地的状态，求出θ的值，然后根据公式（2）确定具有最小分段移动度的路径，并记录路径。

（5）按照时间顺序依次安排分段堆场计划。每安排完一个分段，则堆场状态矩阵更新一次，其对应的堆场节点状态模型也相应更新一次。

（6）根据公式（2）计算方案产生的分段移动度。

（7）遍历每一种方案：对于一种方案，依时间顺序，一次安排一个分段的堆场计划，将各个已经安排好计划的分段产生的临时分段移动量累加，每安排一个分段的堆场计划就将累加值和待比较方案产生的临时分段移动总量比较一次，如果累加值比待比较方案产生的临时分段移动总量小，则继续安排后续分段的堆场计划，否则淘汰该方案；如果该方案的堆场计划已经安排完，产生的临时分段移动量累加值小于待比较方案，则将该方案作为新的待比较方案；如果该方案的堆场计划已经安排完，产生的临时分段移动量累加值等于待比较方案，则计算该方案下平板车在堆场中的移动距离，将其和待比较方案的平板车在堆场中的移动距离进行比较，若比待比较方案小，则将该方案作为新的待比较方案，否则淘汰该方案。

（8）所有方案都遍历完后，最后的待比较方案即为最优方案。依据此方案来安排堆场计划。

5 实例验证与结果分析

5.1 实例验证

以下通过上海某大型船厂记录的半年内每天的天气情况、设备好坏、船东检验与否和进出场段数等信息来预测未来一周内进出场段数。

由经验公式（1）知隐含层节点数在2～12之间，因此设计一个隐含层数目可变的BP神经网络，其结果如表1所示。

表1 隐含层节点数对比

从表1中可以看出，在保证训练误差0.005 0的情况下，当隐含层节点数取11时，其验证样本和检验样本的误差和相关系数最好，因此，本文的神经网络预测模型取11个隐含层节点。

预测结果：未来一周内总的进出场段数为55，其中有37个进场分段（从B82依次命名到B118），18个出场分段，若在一周内某进场分段进场后又要从堆场中出来，则其作为出场分段时，所在位置表示为未定的V00。按时间顺序排列的一周内堆场计划如表2所示。

接下来，为验证所建调度模型及算法的可行性与正确性，利用Visual Studio2010软件，在处理器为1.2 GHz，内存为2 GB的计算机上对模型进行求解。实验包括以下输入参数：（1）堆场尺寸及当前的使用状况，即初始状态；（2）一个周期内，进出场分段的数量、顺序及计划时间。

图6所示堆场有81个作业场地，其中58个场地被占用，Bn为放置在场地上的分段名。

通过算法程序确定进场分段在堆场中的停放位置以及进出场分段从停放位置到道路V0的路径，得到一种较优的堆场调度方案如表3所示。在表3中，每条移动路径的第一个位置节点分别是堆场状态矩阵的行与列）为进出场分段的停放位置。

在实际生产中，分段堆场调度主要是依据调度员的经验进行调度，不仅需要花费大量人力、物力以及时间，且每次只能安排当天要调度的分段，无法考虑到后续的堆场作业计划。利用本文所研究的方法，可以一次安排一周及以上的计划，并且运行算法程序可得到较优的调度方案，充分利用堆场资源，提高作业效率。

表2 一周内堆场计划

图6 堆场的初始状态

表3 调度方案

5.2 数值实验分析

（1）算法比较分析

每个分段进场堆场都需要确定从道路到目标位置间的最短路径。分段进出场路径的选择造成了堆场调度问题复杂性的增强。对于路径的求解可以通过迪克斯特拉算法来优化，Dijkstra算法是典型最短路算法，主要特点是以起始点为中心向外层扩展，直到扩展到终点为止，但其遍历节点的特性增大了算法的耗时。本文将堆场所有节点通过画菱形的方式归入不同的阶段集，将整个路径选择过程划分为几个阶段子过程，从而简化路径选择过程。利用C#软件，在处理器为1.2 GHz，内存为2 GB的计算机上实现迪克斯特拉算法求解分段移动路径。并将迪克斯特拉算法与改进启发式规则进行对比，结果如表4所示。可看出：随着堆场规格的增大，两种算法的耗时都逐渐地提高，但后者的运行时间明显小于前者，并且堆场尺寸越小，本文算法较Dijkstra算法的优越性就更突出。原因是在确定最优路径的过程中，后者不需遍历所有节点，一般在第3或4阶段就能找到最优路径。

表4 算法比较分析（单个分段）

（2）模型可解性分析

在船舶堆场调度问题中，增大堆场的尺寸、增加待调度分段的数量或者降低堆场的初始状态的利用率（即增大初始状态中空场地的个数），都将会提高算法求解的难度，算法耗时也会相应变长。其中堆场的尺寸主要是对启发式算法求解分段的进出场路径产生影响，而后两个因素则增加了进场分段在堆场中的放置位置的可行方案数，从而增大求解空间。对于9列9行的81个作业场地的堆场来说，当分段存在的调度方案数超过93 673 816种时，程序运算时间超过半小时。因此本模型可解的规模有限，适用于中小规模堆场调度问题的优化求解，对于大规模堆场调度问题，可考虑结合问题分解策略，将原问题分解转化成多个中小规模的调度子问题后进行求解。

（3）预测对堆场调度的重要性分析

实际调度中，由于受到扰动因素的影响，系统将被迫进行多次重调度，全局问题将按重调度次数分割为多个局部优化问题，从而影响并降低了调度系统的绩效。通过BP神经网络预测可事先预知未来调度过程中的影响因素，并可事前控制和调整调度计划，从而减轻干扰因素对调度系统造成的影响。实例中，假设全局问题被2次扰动事件先后分割成3个局部调度问题，而由这3个局部调度所得的临时分段移动量分别为13、11和1，其总和25超过了由全局调度所得初始方案的分段移动量21，降低了系统的绩效。

6 结论

本文通过对船舶分段堆场实际情况的了解，作出合理的进出场段数预测，改善不确定环境下的调度计划执行度，并综合考虑了初始利用率、计划分段个数、堆场尺寸等因素，通过建模并采用分支定界法及启发式算法对其进行求解。仿真实验结果验证了方法的有效性和实用性。

[1]Kirn K H，Park Y M，Ryll K R.Deriving decision rules to locate export containers in container yards[J].European Journal of Operational Research，2000，124（1）：89-101.

[2]Zhang Canrong，Chen Weiwei，Shi Leyuan，et al.A note on deriving decision rules to locate export containers in containeryards[J].European JournalofOperationalResearch，2010，205：483-485.

[3]Zhang Weiying，Lin Yan，Ji Zhuoshang，et al.Optimization model of constrainers loading operation in export constrainers terminal[J].Journal of Wuhan University of Technology，2006，30（2）：314-317.

[4]Lee Yusin，Chao Shih-liang.A neighborhood search heuristic for pre-marshalling export containers[J].European Journal of Operational Research，2009，196（2）：468-475.

[5]Chung Chia-Shin，Flynn J，Kirca O.A branch and bound algorithm to minimize the total tardiness for m-machine permutation flow shop problems[J].European Journal of Operational Research，2006，174：1-10.

[6]Jiang Nan，Qian Mai，Qu Hong-tao，et al.Model and algorithm ofcontaineryard operation plans[J].Journalofthe China Railway Society，2009，31（5）：8-16.

[7]郝聚民，纪卓尚，林焰.混合顺序作业堆场BAY优化模型[J].大连理工大学学报，2000，40（1）：102-105.

[8]Yun W Y，Choi Y S.A simulation model for container-terminal operation analysis using an object oriented approach[J].International Journal of Production Economies，1999，59（3）：311-329.

[9]Zhang Chuqian，Liu Jiyin，Wan Yat-wah，et al.Storage apace allocation in containerterminals[J].Transportation Research Part B，2003，37（10）：429-442.

[10]Kim K H，Won S H，Lim J K，et al.An architectural design of control software for automated container terminals[J]. Computer& Industrial Engineering，2004，46（4）：741-754.

[11]Park C，Seo J.Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers& Industrial Engineering，2009，57：1062-1071.

[12]Park C，Seo J.Comparing heuristic algorithms of the planarstorage location assignmentproblem[J].Transportation Research Part，2010，46：171-185.

[13]陶宁蓉，蒋祖华，毛祖杰，等.船体分段堆场调度模型与算法研究[J].机械设计与研究，2011（12）：261-264.

[14]陈雨，陈新，陈新度.不确定环境下的多Agent鲁棒性预测调度研究[J].中国机械工程，2009，16（7）：1937-1942.

[15]李巧云，王冰，王晓明.随机机器故障下单机预测调度方法[J].系统工程理论与实践，2011，31（12）.

ZHOU Jian,CAO Ruixia,WANG Xiong

Department of Industrial Engineering,School of Mechanical Engineering,Tongji University,Shanghai 201804,China

The shipbuilding yards scheduling is overly dependent on artificial prediction and scheduling and lack of effective scheduling approach in practical production.The BP neural network is proposed to predict the number of sections which are shipped in and out in one period.Then a mathematical model is defined as the assignment and paths of the inbound and outbound objects to the shipping yard with aim of minimizing the degree of movement of blocks.Then a branch and bound algorithm is formulated to select the optimal parking positions of blocks.And a heuristic algorithm is also proposed to confirm the optimal moving paths of blocks in the yards.Application data are obtained from a shipyard to validate the model,and the result shows that the proposed algorithm is effective to solve the shipbuilding yards scheduling problem.

heuristic regular;shipbuilding yard;predictable scheduling;branch and bound algorithm

针对船舶分段移动计划主要依靠人为预测及人工调度的现状，提出BP神经网络来预测一个周期内进出场分段的数量，并研究建立以分段移动度最小为目标的优化模型，模型综合考虑了分段在堆场中的停放位置及进、出场路径。通过分支定界法选择分段在堆场中停放位置的最优方案，并构建启发式规则来确定分段在堆场中的最优进、出场路径，从而实现对模型的求解。以某船厂实际数据为例，对模型在堆场调度问题中的应用进行了实例验证，结果表明，所研究方法可求解得出较优的堆场作业计划，并实现堆场资源的高效利用。

启发式规则；分段堆场；预测调度；分支定界法

A

TP393

10.3778/j.issn.1002-8331.1306-0038

ZHOU Jian,CAO Ruixia,WANG Xiong.Shipbuilding yards predictable scheduling approach.Computer Engineering and Applications,2013,49（23）：221-227.

国家自然科学基金（No.70872076）；上海市博士后基金项目（No.11R21416500）。

周健（1975—），男，博士，副教授，研究领域为工业工程；曹瑞霞（1988—），女，硕士研究生，研究领域为工业工程；汪雄（1989—），男，硕士研究生，研究领域为工业工程。E-mail：caoruixia1228@163.com

2013-06-07

2013-08-19

1002-8331（2013）23-0221-07