考虑工艺顺序和组合分段的多堆场调度方法

2020-05-08孟令通蒋祖华陶宁蓉刘建峰

上海交通大学学报 2020年4期

关键词：占用率堆场出场

孟令通，蒋祖华，陶宁蓉，刘建峰，郑虹

(1. 上海交通大学机械与动力工程学院，上海 200240； 2. 上海海洋大学工程学院，上海 201306；3. 上海外高桥造船有限公司，上海 200137)

符号说明:

di,j—分段i允许进出堆位j的方向

Ey—堆场y与道路可直接通行的堆位集合

jy—堆场y中的堆位j

在现代造船模式中，分段作为基本生产单元在完成脱胎后，需经过预舾装、舾装、涂装、总组等工艺流程，最后完成船体搭载.堆场作为分段任务的缓冲地，具有承担了部分后期加工任务的作用，在堆场中可以完成预舾装、涂装等工序.堆场中分段的调度由平板车完成，为了确保调度作业的准时性，减少调度成本，提高堆场作业效率，优化堆场调度策略至关重要.目前，许多传统的调度方式仅适用于单堆场的调度情况，而单堆场调度属于多堆场调度的特例，主要应用于堆场和车间之间的分段流转.传统调度方法虽然可以提高单堆场调度的效率、增加分段调度的合理性，但忽略了分段的工艺流向，并不适用于多堆场调度.然而，船厂内堆场数量众多，分段是在多个堆场和车间之间流转的，因此，设计合理的船舶分段多堆场调度方法是提高船厂内堆场整体调度效率的关键.

多堆场调度并不是单堆场调度的简单叠加，虽然其调度过程也是通过规划分段调度的位置以及路线，进而确定分段任务的执行顺序，但仍有诸多不同之处.

对于四面通行的单堆场调度，平板车的运输路径多为直线.文献[1]以减少无效移动为目标，规划堆场布局和内部通道，用阻挡分段率验证分段调度在船舶生产中的重要意义.文献[2]在文献[1]的基础上重新定义了堆场分段位置的分配问题，以进出堆场阻挡分段为优化目标，设计遗传算法优化分段堆位，提高了堆场调度效率.文献[3]在遗传算法优化分段堆位的基础上，设计进场分段和阻挡分段的启发式移动策略用于求解四面通行堆场的堆位分配问题.文献[4]以阻挡分段数量为优化目标，设计进场分段的堆位选择策略和阻挡分段的移动策略，得出分段任务的执行顺序对调度结果有着重要影响的结论.

在实际应用中，直线运输路径一般用于场地资源不紧张的情况.当场地资源有限时，平板车的运输路径主要为折线.节点状态模型是适用于折线运输的调度模型且其分段形状均为矩形.文献[5]设计了启发式规则以确定分段移动路线，并通过遗传算法优化分段在堆场中的堆位.文献[6]结合了分段质量和移动距离，用双层遗传算法确定分段的调度顺序及其在堆场中的停放位置，并设计了启发式算法规划分段最优移动路线.文献[7]在文献[4]的基础上，以分段移动度为优化目标，针对单面通行堆场设计了5种阻挡分段的移动策略，并用多链DNA遗传算法对分段任务的执行顺序进行求解.文献[8]以分段移动度为优化目标，考虑分段工艺阶段和多堆场堆位优先级，针对多个堆场的分段调度问题，设计了阻挡分段启发式调度规则.文献[9]提出将分段进行组合堆置，但仅研究了组合分段在单堆场中的调度问题，并没有涉及多堆场调度.

针对多规格分段布局的研究大多不划分堆位且调度场景主要集中在分段建造车间内.文献[10]深入分析了分段属性以及加工平台、加工空间、加工流程等各类约束，设计了一种贪婪的启发式搜索算法，并与网格搜索算法和遗传算法进行了对比.文献[11]考虑了不同规格和摆放方向的分段，将问题表述为一个混合整数规划(MIP)模型，设计了调度优先级规则和对角填充空域分配方法.文献[12]同时考虑了分段布局和模糊建造时间，提出用模糊三角时间模型表示不确定的分段开工和完工时间，并设计了遗传算法优化分段加工位置.

以上研究都是只针对单一规格分段、堆位固定且只能容纳一个分段的堆场调度问题，可处理的分段数量和种类较少，简化了分段在各个堆场流转过程中任务的连续性，忽略了分段的工艺顺序.针对上述问题，本文在文献[13]的基础上提出了组合分段多堆场调度模型，考虑堆位内组合分段之间的干涉，设计了多堆场分段堆位选择策略和阻挡分段跨堆场移动策略，以确定分段的目标堆位；改进了传统的任务顺序调整策略，并用禁忌搜索算法进行优化；最后，讨论了不同调度策略对运输成本的影响，并通过实例求解得到多堆场内任务和阻挡分段的多堆场调度方案.

1 问题模型

1.1 问题描述

分段多堆场调度示意图如图1所示，多堆场调度与单堆场调度的差异如表1所示.

图1 分段多堆场调度示意图Fig.1 Sketch of block transportation in multi-stockyard scheduling

表1 多堆场调度与单堆场调度的差异Tab.1 Difference between multi-stockyard scheduling and stockyard scheduling

多堆场调度遵循以下假设：

(1) 堆场均为组合分段堆场，一个堆位可以堆置1个大型分段，或2个小型分段；

(2) 各堆场规格不同，但堆位序号的编码方式相同，从堆场左上角开始依次由左至右、由上至下编号；

(3) 所有分段投影的外包络线均简化为直角梯形，组合分段在一个堆位内按照堆位编码方式左右水平堆置；

(4) 堆场之间由道路连接，不考虑道路宽度对平板车运输的影响；

(5) 堆场外运输先将分段运输至堆场边缘，再进行堆场内运输，且堆场外运输时将堆场视为节点；

(6) 堆场可进行部分后期加工，如完成预舾装、涂装等工序；

(7) 阻挡分段不能再次产生阻挡，待完成后期加工后可以跨堆场调度；

(8) 任务分段和阻挡分段根据下一个工序选择堆场.

1.2 数学模型

多堆场调度主要从两个角度对调度进行优化：① 减少调度过程中产生阻挡分段的数量，降低分段重复搬运造成的资源浪费；② 优化分段移动路线，降低平板车油耗.目标函数将综合这两个方面进行考虑.

决策变量：

目标函数：

(1) 任务分段移动时产生的阻挡分段总数

(1)

(2) 任务分段和阻挡分段在堆场内的运输距离

(2)

(3) 任务分段及阻挡分段跨堆场间的运输距离

(3)

优化目标函数表示为

(4)

式中：wm表示移动阻挡分段的权重；wl表示平板车负载运输的权重.

s.t.

(1) 分段运输在调度周期内执行，

(5)

(2) 堆场中同一个堆位上至多可以堆置2个小型分段.

(6)

(3) 任务分段所在堆场符合分段所处的工艺阶段，分段的下一个工艺阶段是在合适的堆场进行,

(7)

(8)

(5) 分段只能通过堆场与周围道路可直接通行的堆位进出堆场，其余的堆场方向视为围墙禁止通行.若一个6×10堆场只能单面通行且堆场内的分段只能从堆场上方运输出去，可通行堆位集合Ey={0,1,…,9}，对于进出堆场路线的边缘堆位有

(9)

(6) 在执行任务的过程中，进入目标堆场时，不能超过堆场容量，因此需要在目标堆场中找出能满足大型分段或组合分段的堆位，

(10)

对目标函数求解之前，首先要获取各堆场已知的初始状态，包括堆场规格、分段布局和堆场四周的通行情况，分段只能经过堆场与道路可直接通行的堆位(即矩形堆场的某些边)进出堆场.若分段按照策略无候选堆位或堆场已经堆满分段时，则将分段运输到6号堆场，并在目标函数中加入惩罚值Z.

2 模型求解

2.1 组合分段干涉方向判断

利用启发式规则判断组合分段在一个堆位内的干涉方向：在可行的空域内，分段的最终参考点位置要尽可能靠近可行域最左下角的顶点，也就是文献[13]中的最左最下规则.如图2所示，b1为堆位中已经堆置好的分段，需要将分段b1的顶点G1靠近堆位最左下角的顶点；b2是将要与b1组合堆置的分段，顶点G2需要尽量靠近分段b1.因此，分段b1的可移动方向为上、左、下，即移动方向db1,j=j-N,j+N,j-1；当db1,j=j+1时，阻挡分段数量会增加.

图2 可行空域分段堆位最左最下规则Fig.2 The left-bottom rule of feasible space in cell

使用空域的方法，对组合分段通过包络转角进行16种判断，判断过程如图3所示.分段b1通过4次90° 的顺时针旋转调整其在堆位j中的堆置方向(图3(a))，每种b1的堆置方向对应4种组合分段b2的堆置方向(图3(b)).如图3(b)所示，可以组合堆置的方式有0°、180° 两种，因此，在分段组合堆置后，当移动b1时，对应的干涉方向分别为右方(0°)、右方和上方(180°)；当移动b2时，对应的干涉方向为左方、左方和下方.当有多种方式可以堆置分段时，需要选择干涉方向较少的组合方式堆置分段.

实际上，在组合堆位的分段进入堆场的过程中，目标堆位上已有分段的堆置方式已经确定，需要根据不同的组合方式调整进场分段的堆置方向.整个调整过程依靠平板车的液压驱动、液压悬挂、独立转向、车架自动调平等技术完成.需要注意的是本文忽略了因再次调整组合分段位置产生的调度成本.

图3 堆位空间分段组合可行性性判断Fig.3 Feasibility judgment of block combination in cell

2.2 任务执行顺序调整策略

表2 调度周期第t天的任务分段时间余量Tab.2 Time information of block transportation tasks on Day t of scheduling

分段在移动过程中应尽量减少阻挡分段的产生，因此若任务分段的阻挡分段中包含后续分段，则要将后续分段的运输提前.如图4所示，165,175表示计划第5天出场的组合堆置的分段16和17，在实线标出的路径上，3号分段是17号分段的阻挡分段，因此可以将3号分段提前运输.具体步骤如下：

图4 堆场内的分段任务执行顺序Fig.4 Sequence of block transportation tasks in stockyard

步骤1先执行出场分段任务，将任务组内的出场分段按照移动成本进行排序.若成本相同，则按照时间余量进行排序.

步骤2判断后续分段任务中是否存在任务分段的阻挡分段.若有，则将阻挡分段提前至任务分段前执行.

步骤3判断后续分段任务中是否有任务分段的组合分段.若有，则将组合分段提前至任务分段之后执行.

步骤4判断后续分段任务中是否有到当前分段的无阻挡路径.若有，则将分段提前至任务分段之后执行；否则，返回步骤1继续执行任务序列中的任务，直至所有任务执行完毕，得到最终的任务出场执行顺序.

2.3 多堆场分段堆位选择策略

步骤2选择p′

步骤3判断A是否为空集.若A=∅，则将堆位加入A1，进而判断堆位中分段是否可以与任务分段组合堆置；否则返回步骤2，直至A中分段遍历完毕.若可以组合堆置，则将堆位加入A2.

步骤4得到集合A1和A2.

步骤5若A1和A2都为空集，则说明该堆场已经达到堆场容量上限.

候选堆位是允许堆置进场分段的堆位，具体堆位的选择有如下两种策略.

策略1若任务分段是组合分段，则选择候选集合A2中出场时间相同的分段进行组合堆置；若分段是大型分段，或者无出场时间相同的组合分段，则计算每个空堆位与周围分段的平均出场间隔时间

其中：R表示候选堆位四周的分段数量；τht,τr分别表示任务分段和四周各个分段的预计出场时间.选择与周围分段平均出场间隔时间最小的位置作为进场堆位.

策略2综合考虑进场分段对在场分段及空堆位的影响，选择合适的堆位堆置进场分段.堆位候选集合中每个可行堆位在放置任务分段后，需计算当前阶段预计产生的调度成本，并选择对后续分段移动影响最小的堆位，具体步骤如下：

步骤1获取任务分段i的堆位候选集合A1和A2.

步骤3对堆场中的其余分段，将与之相比出场时间较早的分段不计，计算预计产生的出场移动成本α1=∑j′∈A1∪A2(wmnj′+λwldj′).

步骤4对堆场中每个可推置堆位j″∈A1∪A2，同理计算有分段进入该堆位时的预计移动成本α2=∑j″∈A1∪A2(wmnj″+λwldj″)，得到分段i堆置于堆位j对整个堆场的影响指标Vj′=α+α1+α2.

步骤5返回步骤2，直至候选集合中堆位遍历完毕.

步骤6选择Vj′值最小的堆位作为分段i的进场堆位j.

2.4 阻挡分段跨堆场移动策略

在多堆场调度阻挡分段的堆位选择过程中，阻挡分段可以在原有堆场中进行调度，也可以在完成当前堆场的部分加工后直接运输到其他堆场.若需要移动到其他堆场，则要首先确定阻挡分段接下来要被运输的目标堆场.目标堆场可以是符合阻挡分段下一阶段工艺属性的堆场或仅仅是临时堆场，但不能返回阻挡分段当前工艺阶段之前的堆场，否则将影响其他堆场内部的周转，进而增大运输成本.为了降低运输的嵌套性，阻挡分段在位置重新分配的过程中不允许再次产生阻挡分段，只可以选取平板车能够直接到达的堆场堆位.

策略3将阻挡分段就近堆置在原堆场，剔除原堆场中的任务分段路径，选择通行无阻挡的堆位；区分大型分段和组合分段，挑选与周围分段出场时间较为接近的堆位进行堆置.

策略4拓宽阻挡分段的堆位选择范围.根据工艺阶段，确定阻挡分段的堆场，根据阻挡分段对堆场空堆位及在场分段的影响指标确定阻挡分段重新分配的堆场及堆位，其具体流程如图5所示.其中：y′为任务i的当前堆场；A′为阻挡分段移动的堆位集合.

图5 阻挡分段移动策略2的流程图Fig.5 Flowchart of moving strategy 2 with obstructive blocks

2.5 禁忌搜索

2.5.1禁忌搜索结构通过邻域搜索优化任务的执行顺序.设:π为初始解；TL为一个空的禁忌搜索集合；Iter和NIter分别表示总迭代次数和结果没有提升的次数.当Iter≥MaxIter或者NIter≥NonImpIter 时，则终止循环.计算步骤见文献[9].

图6 邻域搜索示意图Fig.6 Illustration of neighborhood search

禁忌搜索表是在搜索过程中为了防止重复循环记录邻域变换的集合，每个任务用(t,m,x1,x2)表示.其中：m表示领域搜索的模式，m=0表示交换模式，m=1表示插入模式；x1,x2表示任务取出后，交换或插入的位置.

3 算例分析

3.1 调度结果分析

为了验证模型以及算法的可行性，本文设计了多组实验对其进行验证.为了提高数据的实用性，所生成的数据在分段规模、堆场占用率、堆场布局等方面均参考了船厂的实际调度数据.程序采用java代码编写，在 3.2 GHz双核处理器、8 GB内存的计算机上运行.

输入参数设定如下：

(1) 调度周期10天；滚动周期2天；分段在堆场中的平均停留时间3天.

(2) 组合及非组合分段数量为200个；堆场初始占用率分别为70%、80%、90%.

(3)wm=1，w1=0.01，当分段按照策略无候选堆位或堆场已经堆满分段时，则将分段运输到6号堆场，并在目标函数中加入惩罚Z=5.

(4) 堆场状态为5个单面通行的堆场.堆场1为4×5；堆场2为5×6；堆场3为5×6；堆场4为 6×10；堆场5为6×10；堆场6为最终的总组堆场，不考虑堆场6内的分段如何移动(相当于节点)，共有200个堆位.堆场编号决定了分段按照工艺要求只能运输到堆场编号较大的堆场，堆场内每个堆位的间距为10 m，堆场布局及初始状态如图7所示，堆场之间的距离如表3所示.

(5) 禁忌搜索中MaxIter=100,NonImpIter=50.

图7 多堆场调度堆场布局实例Fig.7 Example of multi-stockyard layout

表3 堆场之间的距离(m)Tab.3 Distance between multi-stockyard (m)

任务执行顺序策略：① 按照搭载时间余量确定任务的执行顺序；② 改进任务的执行顺序并用禁忌搜索进行优化.

堆场堆位选择策略：① 以平均出场间隔时间最小为依据选择进场堆位；② 综合考虑进场分段对在场分段及空堆位的影响后选择堆位.

阻挡分段移动策略：① 根据工艺阶段，在下游堆场中以平均出场间隔时间最小为依据选择阻挡分段堆位；② 在①的基础上，根据阻挡分段对堆场空堆位及在场分段的影响指标确定阻挡分段堆位.

组合对比任务执行顺序策略、进场分段堆位选择策略及阻挡分段移动策略(共8种策略组合方式)，在新进入堆场的分段数量为0或与进入堆场6的分段数量相同的条件下进行实验.

当新进入5个堆场的分段数量为0时，代表周期内没有中小组立加工成为分段，即没有分段从加工车间运输至堆场；当新进入5个堆场的分段数量等于堆场进入堆场6的分段数量时，调度周期内的堆场平均占用率可以维持在70%、80%、90%左右.组合策略的调度结果对比如表4所示，其中，F为目标函数;r为阻挡分段数量占任务分段的比例.由表4可知：在多堆场调度中，若堆场都是单面通行，则其阻挡分段的比例较高；当无新分段进入堆场时，几种方法r的均值分别在30%、33%、37%左右；当堆场平均占用率保持相对稳定时，几种方法的阻挡分段比例分别在60%、70%、82%左右.

通过对比分析任务执行顺序策略，进场分段位置选择策略和阻挡分段移动策略，可以得到在其他条件相同的情况下，任务执行顺序策略②相比策略①对调度结果有一定程度的提升且始终优于策略①；在堆场占用率较低时，与策略①的目标函数值、阻挡分段数量相近，策略②对于阻挡分段非放回式的多堆场调度并没有较大的提升空间；而当分段数量较多时，任务执行顺序策略②的优化效果较为明显，说明以完成搭载的时间余量规划任务执行顺序只是考虑了分段对搭载的影响，并没有考虑分段在堆场中调度的干涉，而通过改进策略并用禁忌搜索进行优化后能够使任务在执行日期内的排序更加合理.

进场分段位置选择策略②相较于策略①对调度结果的优化有一定程度的提升，说明考虑进场分段对整个堆场影响的堆位选择策略同样适用于多堆场调度.通过考虑相邻堆位分段相对出场时间均值的方式选择堆位，而不是直接根据阻挡分段数量或是移动距离长短进行判断，其相邻分段的出场时间可能较为接近，但在处理组合分段时有一定的局限性.策略①中组合分段只能与出场时间相同的分段进行组合堆置，当堆场较为复杂、占用率较高时，组合分段可选择的堆位较少，可能会出现组合分段独占一个堆位的情况，使调度成本上升.

阻挡分段移动策略②对求解任务目标函数的优化程度很明显.当堆场占用率逐渐递减时，在堆场初始占用率分别为70%、80%、90%的情况下，阻挡分段移动策略②相比于策略①的目标函数值分别有 7.6%、10.8%、11.5%的降低；当堆场平均占用率保持不变时，策略②相比于策略①分别有19.1%、24.6%、37.9%的降低，这主要是由于当保持5个堆场中的分段总数不变时，堆场密度可能出现不平衡，进而造成某个堆场分段占用率很高，而其他几个堆场分段占用率较低的情况.策略①的阻挡分段调度方式极大地增加了堆场本身的负担，因此出现了很多阻挡分段无堆位可放的现象，增加了惩罚，从而提高了调度成本；而策略②将已经完成加工的阻挡分段移动到下一工艺阶段的堆场符合调度的工艺方向，在一定程度上避免了分段过于集中的现象，降低了多堆场调度的复杂性.