复杂形状船舶分段建造空间调度优化算法

王津剑，杜吉旺，范秀敏，2+，何其昌，2

（1.上海交通大学 机械与动力工程学院，上海 200240；2.上海市网络化制造与企业信息化重点实验室，上海 200230）

0 引言

船舶建造作为传统产业，随着精益生产、成组技术等新技术在该领域的应用，催生了新的现代船舶建造模式，在此模式下，船舶以分段为单元制定生产计划并进行生产［1］。分段是由船体的零件、部件组成的局部结构，由于分段建造占用大量空间区域和设施资源，对分段生产进行安排，在满足调度约束的条件下获得最优的动态空间布局即为分段空间调度问题［2］。

船舶分段空间调度是NP完全问题，一般采用启发式调度算法求解。Lee等［2-3］最早对船舶分段空间调度问题进行了研究，提出最大剩余空间利用规则、初始定位规则、边规则和混合规则等启发式调度规则，用时空坐标系对分段进行三维空间调度，基于此开发了韩国大宇造船厂的DAS-CURVE软件。此后，国内外对空间调度算法进行了深入研究并进行了改进。Lee［4］研究了空间调度专家系统的搜索空间，证明了对于投影形状是多边形的分段，以顶（角）点为搜索空间的启发式算法在空间调度上是有效的，但是并没有考虑分段摆放方向。Liu等［5］针对矩形分段，将分段边界延长线的交点增加到启发式算法的搜索空间，但是随着分段的增加，搜索空间的容量急剧增加。Varghese等［6］采用类似于“二维装箱”的算法，采用最下最左（Button Left，BL）的启发式定位策略，计算矩形分段的布局。Shin等［7］先使用矩形计算分段的初步位置，再换上实际形状，调整分段的局部位置，使分段布局紧凑。张志英等［8］采用最小包络多边形的方法对不规则的分段进行多边形处理，采用悬挂检测方法对分段位置干涉进行检测，但是当待布局的分段尺寸较大时，存在将正在加工的分段覆盖的问题，此时悬挂检测方法失效。陶宁蓉等［9］将分段加工的时间窗与时空坐标系相结合，提出基于极点的定位规则，应用工艺簇和形状簇策略解决分段调度序列，改进了空间调度的启发式算法。郭美娜等［10］提出一种基于深度优先树搜索的动态调度方法，在每个时间片内使用局部启发调度算法进行空间布置搜索。张志英等［11］采用改进粒子群算法来优化分段调度序列，获得了很好的效果。马少辉等［12］采用遗传算法对分段的调度序列进行了优化，并对算法进行了验证。这些研究都是在两方面对空间调度算法进行改进：一是优化分段位置定位的策略或逼近分段的实际投影形状，以提高启发式算法的效率；二是优化分段调度序列，以提高分段建造区域的利用率。

以上研究针对的分段投影形状主要是矩形，其形状复杂程度较低。虽然有少数学者研究了形状复杂的分段，但是缺乏有效的分段位置干涉检测方法。目前采用的启发式算法能够解决分段的位置计算，然而不同形状的分段需要不同的启发式操作规则。虽然智能算法用于分段序列优化的效果明显，但都是针对一个分段建造区域，当有多个分段建造区域时，这些算法都没有考虑集中使用部分区域来减少资源的投入。

为了解决上述问题，本文针对复杂形状分段间的位置干涉检测，采用点—射线法进行判断，并将栅格遍历方法和遗传算法相结合，形成两阶段混合调度方法，对包含多个分段建造区域的分段建造调度计划进行调整与优化，并以船厂实例来验证方法的有效性与实用性。

1 问题描述

分段按照生产计划在装焊工场中并行建造，可以缩短造船周期、提高生产效率。然而船厂的场地资源有限，分段并行建造常常无法按照计划执行，分段建造已经成为船舶建造过程中的一个瓶颈，因此需要对分段建造过程进行合理安排优化，以提高场地资源的利用率。

1.1 分段建造区域数学模型

装焊工场由若干个矩形的跨组成，如图1所示。分段在跨上进行建造，建造完成后通过大型液压平板车将其运输到其他区域，完成后续工作。装焊工场的数学表达为

式中：Ji表示第i跨；Li和Bi表示跨的长度和有效宽度；M表示跨的数量。

1.2 分段数学模型

分段一旦在装焊工场中确定位置就不能移动，其所占的位置不能被其他分段占用。分段是放置在装焊工场的工作面上进行建造的，高度信息在空间调度时不考虑。分段在装焊工场的实际占地用其投影形状描述为

式中：Si为第i个分段的投影形状；ni为分段形状序号；（ai，bi，ci，…）为分段的投影尺寸参数，尺寸参数数量取决于分段投影形状，分段的形状如表1中的“实际投影形状”列所示；N为分段的数量。

表1 分段近似多边形和形状参数

分段建造需要在其时间窗内完成，即在最早开工时间E和最晚完工时间F之间开工并完成。分段建造时间窗和分段开工时间T、分段生产周期P满足如下条件：

式中i=1，2，…，N。

分段在装焊工场占用的区域D用坐标和分段形状表示为

式中：Di为第i个分段在装焊工场占用的区域；（xi，yi，ri，Ji）为分段定位点的坐标，定位点是分段的左下点，Ji为分段所在跨的编号，xi和yi表示参考点在Ji个跨上的坐标，ri表示分段的摆放方向（默认方向逆时针转动0°）；Si为第i个分段形状，如图2所示。

1.3 分段空间调度数学模型

为了节约场地和设备资源，分段应该尽量集中布置。单个跨采用场地有效利用率U进行描述和评价：

式中：Ui为第i个跨的有效利用率，sj为j分段的投影占地面积，Ni为第i个跨中的分段数量，ELi为第i个跨的使用长度，M为跨的数量，有效利用率U越大，表示跨的使用情况越好，其示意图如图3所示。

装焊工场有多个跨，其场地有效利用率U和跨的有效利用率存在区别，如式（6）所示，可以将其作为分段空间调度的目标。分段调度计划还应满足时间约束，本文定义为将分段的建造开始时间与制造周期限定在某一时间窗内，如式（7）所示；空间约束是分段投影区域要在装焊工场跨的有效使用区域内且分段投影区域之间不能重叠，如式（8）所示。分段空间调度的数学模型如下：

式中i=1，2，…，N，k=1，2，…，N且i≠k。

2 复杂形状分段空间调度优化算法

分段空间调度的难点在于单个分段空间定位、多个分段调度序列优化。分段空间定位需要解决两个问题，即分段之间的位置干涉检测和分段位置的遍历与选择。完工分段移除也是空间调度算法的组成部分，其实现过程简单，不是空间调度算法的重点。分段位置干涉检测与分段空间定位相辅相成，是复杂形状分段空间调度优化算法的核心内容，具体关系如图4所示。

2.1 分段位置干涉检测

分段空间调度的空间约束要求分段投影之间不能存在重叠区域，即不能出现分段位置干涉。然而分段平面投影形状各异，有些还包含不规则的曲线，这给分段位置干涉检测带来了困难。可以采用“以直代曲”的方法，将这些投影形状用包络多边形进行近似，如图5 中连接点的虚线构成的包络多边形。多边形之间的位置干涉可以通过判断点与多边形的位置关系实现。

对于任意多边形（如图6），以点Q为起点做任意一条射线，如果射线与多边形的交点数是奇数，则Q在多边形内；如果交点数是偶数，则Q在多边形外。图6中，点Q2和Q5在多边形内部，点Q4在多边形外，检测点是否在多边形内需要注意两个问题：①点已经在多边形上，如Q1，此时点与多边形的位置关系已经确定；②做出的射线与图形的交点是多边形的角点，如以Q3和Q6为起点做出的射线（用虚线表示），此时不能判断点与多边形的位置，需要改变射线的方向，如Q3和Q6用直线表示的射线，此时可以判断Q3在多边形内，Q6在多边形外。为了便于检测，射线的方向首选竖直或水平方向，当都不能判断点和多边形的关系时，取与多边形的边平行的方向，极端情况下取任意方向。

判断点与多边形位置关系的流程如图7所示。如果两个多边形存在位置干涉，即存在重叠区域，则它们的某个角点Q在另一个多边形内。分段投影的包络多边形边数越多，近似图形就越接近真实形状，从而增加了分段位置干涉检测的计算复杂度，因此在确保形状精度的同时应尽量减少多边形的近似程度。

2.2 分段空间定位算法

装焊工场跨的工作区域内遍布直立的胎架，这些胎架高度可调，分段就在这些胎架的支撑下建造。胎架之间的间隔是1m～1.5m，分段位置的精度可设置为1m。对装焊工场中跨的工作区域进行网格划分，网格大小为1m×1m，以这些网格点作为分段位置的搜索空间，按照一定的顺序遍历和筛选，就可以得到分段的最优位置。

分段位置确定采用最左最下策略，网格遍历按照从下至上、从左至右的方向进行，如图8所示。如果分段在跨内，且不与其他分段存在位置干涉，则遍历停止；如果不存在分段的合适位置，则换到下一个跨进行遍历。分段位置计算的实现流程如图9所示。

图9中：r表示分段的方向，a表示分段方向的递增值，分段一般呈水平或竖直方向放置，因此取a=90°。如果一个跨中的分段在多个摆放方向都存在合适位置，则计算出这些方向对应分段的重心位置，取重心最左最下对应的分段位置和方向作为最终分段的布局；如果未能成功获取分段的位置，则将分段推迟到下一个工作日调度。

2.3 空间调度混合遗传算法

当多个分段需要同时调度时，它们之间的调度顺序会影响装焊工场的空间利用率。本文采用遗传算法对分段的调度序列进行优化。

同时调度的分段中可能有部分为延期调度，为保证分段建造的进度，这些延期的分段需要优先调度。为了使延期时间越长的分段越优先调度，引入优先级Td，

优先级大的分段优先调度，对于优先级相同的分段，分段的序列是可变的，通过遗传算法对序列进行优化。

2.3.1 编码设计

遗传算法采用多参数级联的符号编码方式。首先对分段进行符号编码（0，1，2，…，m）然后将相同优先级Td的分段编号放置在一起，按照优先级由大到小排列，分段按照编码顺序调度，如图10所示。

其中：分段编号为bi1bi2…bili的优先级都是Tdi，Td1＞Td2＞…＞Tdn，共有n个不同的分段优先级；优先级同为Tdi的分段有li个。

2.3.2 遗传算法适应度函数

遗传算法的目标是使装焊工场的场地等效有效利用率最大，且跨的数量最少，即编号小的跨尽量放置多的分段，其适应度函数f相对于分段空间调度目标函数U进行修正，可取

式中：wj为第j跨有效利用率的权重，M为跨的数量，Nj为第j跨中分段的数量，sj，i为第j跨中第i个分段的投影占地面积，Bj和ELj为第j个跨的宽和使用长度。跨的有效利用率权重满足w1＞w2＞…＞wM，通过赋予编号靠前的跨更大的权重，使其在调度中优先放置分段，减少跨的总使用数量。适应度f越大，表示个体的质量越好。

2.3.3 遗传操作算子

由于采用符号编码方式，传统的交叉算子和变异算子都会使个体出现非法解，需要对其进行重新设计，同时也需要加快算法的收敛速度、增加个体的多样性。

（1）选择算子 为了加速选择而不失公平性，采用最优保存与轮盘赌相结合的策略，随机生成需要选择复制的代数m（m＞1），直接复制适应度最好的个体到下一代，剩下m-1个个体按照适应度的大小采用轮盘赌的方法进行选择复制，从而增加个体的多样性。

（2）交叉算子 采用重复交叉的方式对单点交叉进行改进。例如父代Parent1和Parent2分别是（0，1，2，3，4，9，8，7，6，5），（4，6，8，7，3，9，2，5，1，0），其交叉流程如图11所示。具体步骤如下：①随机生成单点交叉位置；②交换Parent1和Parent2交叉点后的基因，生成中间代Temp 1和Temp 2；③取出Temp 1中相同的基因，交叉点后的基因按照交叉点前的顺序排列，将Temp 2进行同样的处理，从而增加个体的多样性；④交换Temp 1和Temp 2交叉点后重新排列顺序的基因，生成子代Child1和Child2。

（3）变异算子 在同优先级区域随机产生两个变异位置k和q，对k和q位置上的基因进行互换变异。

2.4 空间调度算法实现

复杂形状分段空间调度算法主要实现开工分段调度和完工分段移除，算法流程如图12 所示。图12中，t（单位：d）为调度时刻，t0为调度起始时刻；Δ为调度时间间隔，通常取Δ=1d。空间调度以天为调度循环间隔进行，所有分段完成建造之后空间调度结束。空间调度循环步骤如下：①进行开工分段调度，提取t时刻开工的分段后用遗传算法对调度序列进行优化；②按照调度序列对分段进行空间定位，如果分段存在位置，则将其添加到“已开工分段”，否则将其开工时间推迟Δ后重新放回“未开工分段”；③更新场地布局，并将调度信息写入“分段调度信息”，完成开工分段调度后，进行完工分段移除，提取t时刻完工的分段，并将这些分段的信息追加到“分段调度信息”，更新场地布局。

3 案例验证与算法比较

3.1 案例验证

为了验证复杂形状分段空间调度算法的有效性，选取上海某船舶企业的实际数据进行计算分析。遗传算法中的各参数取值如下：最大迭代次数50，种群规模取调度分段数的4倍［13］，交叉概率0.5，变异概率0.2；装焊工场中的跨2个，长度150m，有效宽度25m；分段数量86个，分段的近似多边形及其形状参数描述如表1所示，部分分段形状和生产计划如表2所示。

表2 分段形状和生产计划（部分）

续表2

采用VS2010 MFC软件作为编程工具，实现复杂形状分船舶分段空间的调度算法，并绘制装焊工场动态的布局。算法使用不同的初始化种群，对上述86个分段进行调度优化，共进行10次实验，每次实验都得到了较好的结果。表3统计了第一天调度遗传算法的适应度收敛值。

表3 10次遗传算法适应度收敛值（2014-3-1调度）

图13给出了表3中的最优解收敛过程，最优解适应度值为0.874。由图可知解的集合是逐渐收敛的，在25代后个体多样性开始消失，最优解开始收敛。结果表明，依据本文设计的分段空间调度算法对装焊工场进行空间调度，可以提高调度期间装焊工场的有效利用率。

本文算法采用有效利用率对装焊工场的利用情况进行分析，而一般情况则使用平均利用率评价一段时间内装焊工场的利用情况，平均利用率是场地每天利用率的平均值，td的利用率U（t）定义为

式中：M为跨的数量，Ni（t）为t时刻第i跨中的分段数量，Bi和Li为第i跨的长度和宽度，S（i，j，t）为t时刻第i跨中的第j个分段面积。等效利用率越大，装焊工场在相同时间段内的分段布局越紧密，放置的分段越多，场地利用率也越大。

对空间调度优化中装焊工场的利用率进行统计，计算平均利用率，可知装焊工场的平均利用率达到0.800，如图14 所示。对优化结果进行统计，统计结果与实际生产调度利用率的对比如表4所示。实际生产调度时场地平均利用率一般只有0.6，而且分段的占地面积使用的是矩形面积，如果使用实际分段投影形状，则场地的平均利用率将小于0.6。可见采用本文所提算法能够很好地解决复杂形状船舶分段空间调度问题。

表4 空间调度优化与实际调度结果比较

图15所示为装焊工场部分的布局图。图15中3d 的装焊工场有效利用率分别为0.845，0.870，0.841，场地利用率分别为0.471，0.847，0.833。最大等效利用率超过0.87，最大利用率超过0.84，可见本文所提方法可以有效提高装焊工场的利用率。调度第一天（如图15a），进入分段的数量有限，不能占满装焊工场，分段都集中放置在第1跨中，第2跨中的分段也是集中在跨的左侧，从而可以集中使用装焊工场的设备；图15b中的分段数量较多，几乎完全占据了装焊工场；图15c中的分段与分段之间留有间隙，因为调度时装焊工场中存在的分段将跨空闲区域分割成若干区域，部分区域太小，不能放置分段。

3.2 算法之间比较分析

为了进一步验证算法的有效性，对比了4种算法的实验结果，如表5所示，其中延迟开工指分段开工时间T大于最早开工时间E，即T＞E。算法1即为本文采用的算法。算法2与算法1之间的区别在于分段调度序列排序方式不同，算法2采用常规的按最早交货期（Early Due Date，EDD）升序排列的方式，而算法1则基于遗传算法排列；算法3与算法1的区别在于分段位置的搜索方法不同，算法3的分段定位方式采用文献［4］中的分段位置搜索空间的方法，即将跨的角点和跨内分段的角点作为待定位分段位置的搜索空间，而算法1采用的是栅格遍历的方法；算法4与算法1的区别在于分段定位策略不同，算法4采用的是文献［6］中的分段定位点BL策略，而算法1 采用的是分段重心最左最下的策略。

表5 算法结果对比

从表5可见，本文所提算法1在装焊工场利用率、完工时间和延迟开工分段等性能指标上均最优。与算法2相比，算法1采用遗传算法对调度序列进行优化，性能指标上占优。算法3性能较差，虽然也采用了遗传算法对调度序列进行优化，但是对于复杂形状的分段，取跨和跨内分段角点作为位置搜索空间明显不够，还需要通过其他方法扩大搜索空间，然而扩大搜索空间的过程十分麻烦，远不如采用栅格遍历的方式便捷。算法4的性能较差，主要原因是分段定位点的BL策略不适用于复杂多边形形状的分段。

4 结束语

本文对复杂形状的船舶分段提出了统一的位置干涉检测方法，最后采用栅格遍历搜索方法，在保证分段位置精度的基础上更好地解决了复杂形状的分段的位置分配问题；通过改进的遗传算法对分段的调度序列进行优化，提高了场地的利用率。采用实例进行计算，分析了算法的收敛性、装焊工场地利用情况和分段布局，并与其他算法进行了比较，验证了本文所提算法和分段位置干涉方法的有效性。但是，本文提出的算法是在理想情况下，不考虑分段建造的影响因素，这些因素使实际调度结果和算法计算结果存在较大的差别，后续研究将从分段建造的影响因素出发，进一步提高算法的实用性。

［1］ZHANG Guangfa，LIU Yujun，JI Zhuoshang.Simulation and optimization of ship block-building planning［J］.Computer Integrated Manufacturing Systems，2011，17（12）：2643-2651（in Chinese）.［张光发，刘玉君，纪卓尚.船舶分段建造计划仿真与优化［J］.计算机集成制造系统，2011，17（12）：2643-2651.］

［2］LEEK 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.

［3］LEEJ 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.

［4］LEEK J.Sufficient search space for spatial expert systems［J］.Expert Systems with Applications，2000，19（1）：1-8.

［5］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.

［6］VARGHESE R J，YOON D Y.Dynamic spatial block arrangement scheduling in shipbuilding industry using genetic algorithm［C］／／Proceedings of the 3rd International IEEE Conference on Industrial Informatics.Washington，D.C.，USA：IEEE，2005：444-449.

［7］SHIN J G，KWON O H，RYU C.Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution［J］.Production Planning &Control，2008，19（6）：605-615.

［8］ZHANG Zhiying，YANG Kekai，YU Jinwei.Two-dimensional irregular spatial scheduling method for hull block construction in shipbuilding［J］.Journal of Shanghai Jiaotong University，2012，46（4）：651-656（in Chinese）.［张志英，杨克开，于瑾维.面向船体分段建造的二维不规则空间调度方法［J］.上海交通大学学报，2012，46（4）：651-656.］

［9］TAO Ningrong，JIANG Zuhua，LIU Jianfeng.Spatial scheduling problem with time window constraint for block assembly in shipbuilding［J］.Computer Integrated Manufacturing Systems，2010，12（16）：2674-2679（in Chinese）.［陶宁蓉，蒋祖华，刘建峰.带时间窗约束的船体分段空间调度问题［J］.计算机集成制造系统，2010，12（16）：2674-2679.］

［10］GUO Meina，LI Bo.Dynamic spatial scheduling approach based on tree-search［J］.Computer Engineering and Application，2007，43（14）：180-183（in Chinese）.［郭美娜，李 波.基于树搜索的一种动态空间调度方法［J］.计算机工程与应用，2007，43（14）：180-183.］

［11］ZHANG Zhiying，YANG Kekai，YU Jinwei，et al.Dynamic spatial scheduling approach based on improved particle swarm optimization algorithm［J］.Journal of Harbin Engineering University，2009，30（12）：1344-1350（in Chinese）.［张志英，杨克开，于瑾维，等.改进粒子群算法的动态空间调度方法［J］.哈尔滨工程大学学报，2009，30（12）：1344-1350.］

［12］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（in Chinese）.［马少辉，王景秋，陆春霞，等.动态空间调度的混合遗传算法［J］.运筹与管理，2013，22（2）：99-104.］

［13］LIU Xiaoxia.Research on the effects of population size on genetic algorithm performance［D］.Baoding：North China Electric Power University，2010（in Chinese）.［刘晓霞.种群规模对遗传算法性能影响的研究［D］.保定：华北电力大学，2010.］