基于虚拟流水的船舶曲面分段建造空间调度方法

李京生，王爱民，唐承统，卢治兵

（北京理工大学 机械与车辆学院，北京 100081）

1 问题的提出

船舶建造过程体现为大量分段的焊接装配，一般按照几何形状特点分类为平直分段和曲面分段。其中，主要由船舶艏部和艉部分解而成的曲面分段具有复杂的几何形状，在生产过程中需要受大量约束的限制，如场地面积、加工人员和制造设备等。由于曲面分段属于大型装焊类生产，多采取产品固定、人员流动的生产形式，即曲面分段根据平面投影占据场地、人员等建造资源，根据需要面向各个分段进行装焊等生产，其中场地和人员是核心的建造资源。当前调度人员主要凭借个人经验制定计划调度方案，通过船舶分段搭载网络计划图，根据曲面分段图形按照一定规则逐一进行分段空间安排。但是手工作业模式无法处理大量分段的排产需要，造成场地利用率和分段生产效率降低，已经成为船舶曲面分段生产过程中亟需解决的瓶颈问题。因此，本文针对曲面分段的场地空间分配调度过程中分段轮廓复杂、数量巨大、制造场地面积有限的特点，提出一种基于虚拟流水方式的实现船舶曲面分段空间布局调度的方法，旨在辅助调度人员获得优化的分段场地面积分配调度方案。

所谓虚拟流水的本质是生产任务的均衡，保证建造资源（人员、焊接设备等）按照固定的节拍进行流转生产，即场地资源内用于生产不同工序的建造资源能够在各个分段之间进行无空闲流转，在完成某一分段的工序任务后，直接开始下一个分段同类工序的生产任务，形成建造资源围绕各个分段的“流水式”生产。例如，对于曲面分段建造中的焊接和涂装典型工序，可以通过分析场地内的工序任务量实现分段建造顺序和建造任务的均衡安排与分配，使得焊接人员完成第一个分段焊接任务后，直接进入第二个分段开始焊接工序，同时第一个分段开始涂装。当第二个分段完成焊接任务后，第一个分段涂装也同时完工，涂装人员便直接开始第二个分段的涂装工序，工序之间形成无间隙对接，最终形成类似虚拟流水式的建造资源流转形式。需要指出的是，由于分段建造过程中主要使用的焊机、喷枪等设备属于便携式资源，建造资源的核心是人员，资源的流转本质是人员携带焊机等资源的流转。虚拟流水的运行原理如图1所示。

图1展示了由建造资源构成的专业化加工人员在不同工位上的曲面分段之间流动，实现固定工位的流水线作业生产。

优化的空间分布调度方案对船舶曲面分段的生产具有举足轻重的作用。对于船舶空间布局调度问题，前人已经展开了一些研究。为了缩短分段建造周期，避免分段建造过程中出现的人力资源由于分段建造顺序安排不合理而造成待工和窝工的现象，仿效普通生产过程中流水生产方式的虚拟流水生产技术的研究正在得到重视。张志英等综合考虑分段交货期和人员等资源约束，提出基于遗传算法的虚拟流水生产调度技术［2］；韩文民等给出曲面分段生产的定量描述以及作业小组的调度机制，建立了基于虚拟流水曲面分段生产的多功能混合流水线数学模型［3］；曹大鹏等借鉴准时制（Just in Time，JIT）的思想，在对工序作业量进行比较的基础上选择相应的作业班组，采用控制看板管理的方法控制各工序间的均衡生产［4］；江志斌等提出采用Petri网建模技术的方法，对虚拟流水线生产关键技术中的作业负荷均衡技术进行了研究［5］。曲面分段场地空间调度由于具有复杂的时空约束和复杂的分段外形轮廓限制，对空间调度算法提出严格的要求，针对分段的空间布局，学者们已经进行了大量的研究。例如：针对曲面分段场地分配部分，Lee等提出基于规则曲面分段空间调度方法［6-7］；张志英等提出基于自适应时空调整策略的调度方法［8］；王蕾等提出采用搭界、剩余加工时间相近搭边等定位规则的空间调度技术［9］；Raj等利用线性规划进行求解，但求解规模有限，无法应用于大规模计算［10］；郭美娜等提出基于树搜索的两阶段调度方法，该方法本质上是先时间后空间的分解策略，目标均为空间的利用率最大［11］；Zheng等提出将空间调度进行模块化处理的方法，采用网格对场地和分段进行分解，通过细化空间对曲面调度进行简化，逐步得到整体调度方案［12］；Venkataramanaiah以缩短生产制造周期、降低空闲时间为目标，开发了基于模拟退火算法的调度方法［13］；Shin等提出基于底层填充启发式算法的分段顺序排布顺序策略，同时提出基于启发式分配算法的分段自动调度机制［14］；Ryu等提出以支持空间调度和工作负荷平衡为目标的空间调度方法，该方法能够取代调度人员的手工调度，完成调度方案数据的管理［15］；Stoyan等为分段图形建立了一种数学分析机制，将圆形和多边形进行抽象处理，形成最小空间占用区域，完成优化空间调度排产［16］；Liu等提出以缩短人员加工时间为目标的曲面分段生产调度模型，通过运用统计学方法对多个分段排布策略进行分析，从而找到最优空间调度方案［17］；Yagmahan等提出多目标空间调度机制，讨论了制造周期、流转时间和设备空闲时间，从人力资源的角度对调度方案的形成进行了研究［18］。

上述文献针对曲面分段调度问题进行了研究，但在下述几方面还需进一步改进和完善：

（1）针对虚拟流水方式的研究有待深入。上述研究虽然平衡了工序间的生产能力，但是没有与场地内分段实际的生产过程相联系，未能有效建立分段空间调度与建造资源间的关系，造成两者无法兼顾。目前开展的虚拟流水式生产模式和生产调度方面的研究，主要偏重于理论模式以及专门针对人员班组的定性安排分析，而对于曲面分段建造同时具有的场地空间及人力配置高度耦合的问题，如建造周期随操作人员数量的变化而提前或延后将导致对场地占用的变化，有必要从时空耦合与场地—人员协调配置的角度开展研究，以推动虚拟流水式生产走向实际。

（2）传统的曲面分段布局算法对生产实际约束进行了简化，降低了布局结果的可用性。例如多边形分段被抽象成矩形，将不规则多边形曲面分段布局变为矩形布置问题，偏离了曲面分段空间调度对不规则图形进行位置分配的本质，难以有效提高场地利用率。同时，还存在简化场地的问题，例如将场地面积划分为不同的区域，使得分段的排布只能在固定区域内进行，以降低不规则图形的拼接难度或者直接忽略不规则图形的拼接。

（3）布局算法应更多地结合船舶生产的实际情况。船舶曲面的制造过程有其自身的特点，单纯的套料算法难以适用于船舶曲面分段场地布局分配过程。例如：分段的排布顺序需要按照实际生产进程进行不断调整；场地具有的动态性特点使其可用面积会随时变化；分段在完成生产后必须调离场地，剩余面积需要继续占用，一次性的布局分配无法满足船舶生产的需要，必须进行基于碰撞检测的持续性调度。

因此本文提出一种实现船舶曲面分段空间布局调度的方法。该方法在满足船舶生产实际的前提下，以提升曲面分段场地利用率为出发点，以分段几何形状拼接为思路，以虚拟流水生产理论为指导，采用图形碰撞检测和布局优化分析规则的综合集成方法，形成以面向曲面分段建造固定工位的人员分配机制、空间调度方案与场地、人员资源相关联的技术思路，解决分段建造任务-资源关联解耦问题，提出曲面分段碰撞检测算法，在更高的分段几何外形建模精度下，解决不规则曲面分段进行空间调度的问题。提出曲面分担场地位置分配算法，通过动态分析场地资源可用面积和分段碰撞状态，实现空间调度的持续调整，并提高算法的运行速度，解决场地内部高效的多次空间调度问题。最终建立面向曲面分段生产的基于规则的空间布局调度方法，完善曲面分段空间布局调度的理论和方法，并开发了相应的调度系统，验证了调度算法的可用性。

2 问题模型分析

曲面分段建造中，分段体积庞大，在进入生产场地后直到完成加工才被吊离，由此产生了分段建造独有的时间和空间相互耦合的复杂问题，即曲面分段建造周期影响场地使用，同时建造资源分配影响建造周期，从而使场地空间与建造资源形成一种相互制约的关系，因此良好的空间调度方案不仅需要保证场地利用率，还必须兼顾建造资源分配，从而保证空间调度方案的可用性。在进行调度算法构建之前，根据曲面分段调度的特点，在提出相关假设的前提下，对问题模型进行分析和描述。

本文对曲面分段的建造过程研究分别从曲面分段场地内的建造过程和空间调度两方面展开。同时从曲面分段的几何建模、场地内分段生产过程和调度目标出发，提出对调度过程的假设，并在此基础上构造调度过程需要的基本数学模型，从而明确调度方法研究的问题域。

2.1 曲面分段几何建模问题描述

船舶曲面分段具有复杂的几何外形轮廓，其集合投影一般为凸多边形，如梯形、三角形和四边形等，由于分段较少存在凹陷部分，即使存在凹陷部分，也由于面积较小、很难插入其他分段，故提出以下假设并构建几何模型：①曲面分段凹陷部分无法进行空间调度，因此对凹陷区域采用忽略端点的方法进行填充。②分段的几何投影可作为其空间调度的几何依据，因此可通过几何投影等缩小比例，获得曲面分段的外形轮廓，并以外形各个端点的坐标顺时针建立分段外形轮廓数据结构。曲面分段利用端点的坐标集合表 述 为（a（x，y），b（x，y），c（x，y），d（x，y）），如图2所示。③分段在场地内存在安全距离，因此对分段每个端点的坐标进行扩大处理，即X和Y坐标分别增加0.5，防止由于分段距离过近而影响正常生产。

2.2 场地内曲面分段生产过程描述

场地内部的曲面分段生产过程与机加生产在本质上具有相同点：曲面分段的制造过程具有分段工位固定、建造资源（加工人员构成的生产班组，以及焊机、油漆等制造设备）流转于各个分段的特点；机加生产过程属于设备固定、加工零件流转于设备之间的类型；同时，在生产场地内部，曲面分段布局必须避免碰撞干涉。因此提出以下假设：

（1）tei（t+1）-tsi，t≥ti，t，i∈n，t∈m。

假设同一时刻同一分段内只允许加工一道工序，式中：tei（t+1）为分段i工 序t+1 的制造 结束时间，tsit为分段i工序t的制造开始时间，ti，t为分段i工序t的加工时间。

（2）rxit=1时，rylt=0（l∈n，x∈Y∩y≠x）。

表示资源约束，假设同一时刻同一建造资源只能加工一个曲面分段的一个工序。

（3）teit≥tei（t-1）+ti（t-1）。

假设曲面分段的第t道工序必须在t-1道工序完成后才能开始生产。

2.3 曲面分段建造目标描述

构建分段建造的目标是为分段调度问题提供标准，主要考虑场地和建造资源两方面。此处假设场地可利用面积固定，建造资源中的便携式加工设备能力无限，人力资源为瓶颈资源。

式中：Iv为场地资源占用量为场地中曲面分段面积的总和，ZS为利用最小包络面积规则对分段占用区域进行分析后得到的场地面积。因此，Iv越小，说明曲面分段相互拼接得越紧密。本文在技术思路中对最小包络面积规则进行了阐述。

式中IT为场地内部的不同分段相同工序的开始时间和结束时间的时间差总和，其数值越小，说明建造资源的闲置时间越短。

式中：I为曲面分段建造总体目标，p1和p2分别为场地资源和建造资源的权重系数。

建立制造目标的目的是明确建造资源和场地资源在分段建造过程中的关系，两者不但构成了曲面生产的两个核心因素，而且在制造过程中也相互影响，其中分段建造周期会影响分段占用场地资源的时间，场地内分段的加工顺序会对建造资源均衡产生影响，因此本文建立了以上述两种因素为目标函数的空间调度方法。

3 基于虚拟流水方式的船舶曲面分段建造空间调度方法

本文针对船舶曲面分段生产调度中存在的问题和特点，提出空间调度方法的总体框架，包含四部分：基于虚拟流水的分段建造顺序排布、曲面分段碰撞检测、基于规则的分段位置优化分析以及基于虚拟流水的人力资源分配方法。

如图3所示，调度技术流程中的四个部分相互联系：①虚拟流水生产方式是制定分段建造顺序的指导思想，结合分段实际生产过程中需要的建造资源，通过建造资源在分段之间的周转，形成适应产品固定工位生产模式下的流水式运行效果，实现分段视角的无等待连续生产，提高分段建造的专业化程度和建造资源的利用率；②分段碰撞检测方法是空间调度的核心，分段在场地内部进行位置分配时，必须时刻检测其是否与其他分段或者场地边界发生碰撞，一旦发生碰撞便需要应用碰撞处理机制进行处理；③基于规则的优化位置分析是空间调度的主体，负责从分段不发生碰撞的位置中为每个分段筛选出最佳位置，最终形成空间调度方案；④基于虚拟流水的人力资源分配是场地内建造人员分配的依据，当分段进入场地内进行建造时，可根据实时的生产执行进度和现有任务对某一分段内的人员数量进行调整，并合理分配部分人员至其他分段，均衡制造节拍，同时反馈场地内的资源占用情况，实现人力资源流转于各个分段工位的最终目标。

4 技术思路

4.1 曲面分段建造顺序分析方法

船舶的船体由大量曲面分段通过焊接组装而成，其装配顺序必须严格按照搭载网络图进行，因此曲面分段必须按照一定顺序进行生产，从而满足船体装配的需要。与此同时，由于分段无法像普通制造一样，工件流转于制造设备之间，而必须令建造资源流转于各个分段之间，形成与传统机加流水生产不同的虚拟流水方式。如前文所述的虚拟流水生产方式，建造资源在各个分段之间不间断地流转，当分段的某道工序完工后，直接转移至其他分段进行制造，避免资源闲置。分段建造顺序分析技术作为实现虚拟流水生产的保证机制，根据当前场地内已排布分段的建造资源分配现状，与即将排布的分段所需资源进行分析均衡，为整个场地布局调度进行初步规划，制定出分段的加工顺序，辅助后续空间调度和建造资源调度方案的制定。

分段建造顺序分析方法包括以下步骤：①进行空间调度与基础数据的交互工作，如分段的图形信息、分段建造信息即分段工艺信息、制造周期及建造资源分配现状、分段场地信息。曲面分段的排布顺序主要依据分段的下发时间、完工时间和加工优先级等因素，对分段进入场地排布的顺序进行初步筛选，以便在后续进行场地分配中按此顺序加入场地中，完成分段的位置安排。②以分段建造信息和场地生产现状为依据，利用分段顺序的筛选公式，计算每个分段的排布顺序系数：

式中：

Zi为曲面分段建造顺序系数，该系数越小，分段的优先级越高；

wh1，wh2和wh3分别为建造周期、人力资源均衡和场地剩余面积比值的权重，三者的值一般根据经验确定；

Bi为曲面分段i的可开始加工时间，Di为曲面分段i的交货期时间；

M为场地中已有每个分段建造生产所需的建造资源数量，Mi为分段i在制造过程中所需的建造资源数量；

S为曲面分段几何图形面积，Q为分段排入场地的面积，Q-∑S为场地中除去已排布分段的面积综合。

分段建造顺序筛选公式的本质是目标函数通过评估分段建造任务与场地内分段建造的匹配程度，决定分段建造顺序。根据场地内已有分段的制造信息，分析后续分段在加入场地后对现有制造任务均衡的影响，最终筛选出适合加入场地内生产的分段。

综上所述，根据公式计算出每个分段的排布顺序系数，按照升序进行排布，即可得到分段建造顺序，形成如图4所示的曲面分段建造过程，该图呈现出建造资源流转于各个分段的流水生产形式。

4.2 曲面分段图形化碰撞检测技术

该技术针对曲面分段的几何形状完成分段的图形化处理和监控机制的建立，为后续分段在场地中与其他图形以及场地边界的碰撞构建几何图形基础，进而确定分段的场地位置。碰撞检测技术流程如图5所示。

该技术的具体流程为：将曲面分段的几何信息以端点集合的形式进行描述，对集合中包含的每个坐标点，按照顺时针的方向进行连接，构成所需曲面分段的外围轮廓，此处将集合中第一个点作为该分段的定位基准点，以便于数据库的存储和读取；接着，采用逐点判断的方式判定几何图形间是否发生碰撞。判定步骤如下：

步骤1 以待判定曲面分段的端点集合为待判定集合，从中选取一个端点P。

步骤2 以点P为出发点，向剩余场地沿X轴的正方向做一条射线，计算该射线与场地以及已排布分段边界碰撞的次数N。

步骤3 判定该次数，如果端点在其他图形外部，则N／2=0；如果端点在其他图形内部，则N／2≠0，直接跳出循环，进入步骤5；否则返回步骤1，重新加载曲面分段的下一个端点。

步骤4 待判定分段的所有端点完成循环后，判定该分段没有发生碰撞，反馈结果并结束循环。

步骤5 待判定分段与其他分段或场地边界发生了碰撞，反馈结果并结束循环。

4.3 分段场地位置分配技术

该技术提出被加入场地分段与其他分段或场地边界发生碰撞后的处理机制，步骤包括碰撞处理和位置分配两部分。整体流程如图6所示。

碰撞处理部分主要应用于分段初始位置的遍历过程，在遍历中将所有不与其他分段或场地边界发生碰撞的分段位置加入至待确定位置集合，为后续最后位置的确认奠定基础。位置分配部分对所有分段在场地内部的可行位置进行筛选，通过计算最小包络面积的优化规则确定分段在场地中的具体位置。

场地位置分配技术的具体流程如下：

步骤1 以现有场地边界为依据，建立场地边界的集合C，集合中的元素为每个边界线段的起始点和结束点坐标，从中选取一个边界Cd。

步骤2 将待分配分段的定位基准点移动至Cd的起始点，沿边界点起始点到结束点的方向移动，在移动的过程中对分段是否与其他分段发生碰撞进行判断，如果与已有边界块发生碰撞，则对碰撞点的位置进行判定，判定公式为

如果标志点Stx大于分段定位基准点Py，则说明分段点在边界左侧，根据分段移动方向应该为远离碰撞边界的原则，继续向分段的左侧移动，直到不发生碰撞。该移动方式还适用于Y轴方向上的判断，只需调换碰撞坐标点的X和Y轴的顺序即可。式中：Cd｜Sx表示边界点中起始点的X坐标，Cd｜Ex表示边界点中结束点的X坐标。式（2）本质上为一个分段是否完成从边界起点到终点的碰撞搜索提供了判定依据，算法中将其抽象为便于应用的具体公式。该算法通过遍历分析场地面积，将场地内已有分段的轮廓归结为边界，通过不断缩小场地内的可用面积，完成场地空间调度，因此必须使用有效的方法判定分段是否沿已有边界完成了分段碰撞检测，一旦发现分段在此边界上没有发生碰撞，便记录分段位置，进入后续步骤。

步骤3 当分段处于不与任何边界发生碰撞的位置后，记录此位置，返回步骤1，选择下一个边界边进行碰撞检测，继续遍历稳定位置，直到分段所有边界都完成碰撞检测。

步骤4 通过分段位置确定规则对分段稳定位置中的点集合进行筛选，分别将分段位置代入最小包络面积规则中进行计算，得到由式（3）计算出的指标值，筛选出最终位置作为该分段的位置。其中最小包络面积规则即以所有分段位置中纵坐标不同且横坐标最大的点为包络点，建立包络点集合，将集合中的点首尾相接构成包络图形，通过公式计算出包络面积。再将包络面积与包络范围内分段的总面积的比值作为判定标准，比值越大，说明包络面积内的空白区域越少、场地利用率越高。比值计算公式为

式中：Pi，j为分段在场地构成图形的外围包络点，由图形分析算法得到，Pi（x，y）为P点的x和y坐标；ba为包络范围内曲面分段的面积；m为包络面积外围包络点的总数；n为包络范围内所有分段的个数。

其中包络面积最小的分段位置即为最佳分段位置，将此位置保留并删除其他分段位置。式（3）是以分段包络区域内的空闲面积最小为目标，利用几何面积计算方法完成构建。

步骤5 当分段位置确定后，必须对场地边界进行重新分析，将新加入的分段与原场地形状进行拟合，重新计算场地边界形状，从而简化分段碰撞检测步骤，直接检测分段与场地边界的碰撞，即可完成分段位置的筛选。

4.4 基于虚拟流水的人力资源分配方法

该方法是以模型问题分析中提出的建造目标为依据，保证实现场地内的人力资源进行虚拟流水生产的手段。通过均衡场地内已有的和新加入分段的人力资源数量调整分段工序内的员工数量，进而延长或加速工序建造周期，实现资源围绕固定工位展开流转式生产。

依据上文模型问题分析中的建造目标，构建人力资源分配方法的具体步骤如下：

步骤1 监测每一分段，将分段中前后工序加工时间存在间隙的分段加入可调配分段集合中，作为目标搜索分段。

步骤2 在所述可调配工序段集合中选取一个目标搜索分段，若可调配工序集合为空则进入步骤7。

步骤3 监测该目标检索分段每一工序的前一工序的结束时间、该工序的开始时间、后续工序的开始时间。

步骤4 调整该工序的工作人员个数，从该工序中抽调一名工作人员，判断此处工序的加工时间是否满足式（4），如果满足则转步骤5，否则转步骤6。

步骤5 将该工作人员名单添加到可调配工作人员集合中，返回步骤3。

步骤6 该分段无法继续抽调人员，将其从可调配工序段集合中删除，返回步骤2。

步骤7 人员调整结束，跳出循环。

式中：Si，j为分段i工序j的开始时间；Ei，j为分段i工序j的结束时间；Cj为加工工序的生产效率；nj为此工序对应的加工人员的数量。

5 算法详细设计

基于虚拟流水的曲面分段空间调度方法的核心思想是综合制定曲面分段建造资源调度方案与空间调度方案，实现建造资源无空闲生产、场地资源充分利用、分段建造无等待连续生产的目标。通过分段建造顺序分析方法控制分段进入场地内部的顺序，同时利用启发式规则实现快速、高效的二维不规则外形的分段空间调度，最终完成建造资源和空间调度方案。

根据上述分析，基于虚拟流水的曲面分段空间调度方案的具体步骤如下：

步骤1 输入场地资源、建造资源，以及曲面分段几何和工艺信息。

步骤2 遍历分段工艺信息，按照分段下发日期、交货期和加工优先级等因素，对分段进入场地内部的顺序进行初步筛选，建立待调度分段序列，将位于序列首位的曲面分段安排入场地。

步骤3 根据分段建造信息和场地内已有的分段建造执行信息，利用人力资源分配方法对场地内的分段建造调度方案进行规划，进而计算待调度队列中的分段的排布顺序系数。

步骤4 选择排布系数最大的分段，依据碰撞检测技术和场地位置分配技术为其分配制造场地。

步骤5 完成该分段场地位置分配后，将该分段从待调度分段队列中删除，同时根据建造资源状态计算分段结束时间，将分段的开工和加工时间点存入建造资源调度方案，将分段位置信息存入空间调度方案，重新计算队列中的分段顺序系数，进而决定后续分段进入场地的顺序。

步骤6 如果场地内部仍然有剩余空间，则返回步骤3，继续为分段分配场地资源，如果待调度分段队列为空，则进入步骤8。

步骤7 如果场地内无法继续安排分段，则遍历建造资源调度方案内部分段结束时间，找出最早结束时间的分段，将其从场地内部删除，返回步骤3，继续安排待调度集合中的分段，如果待调度分段队列为空，则进入步骤8。

步骤8 调度结束，输出建造资源调度方案和曲面分段空间调度方案。

6 算法复杂度分析

设曲面分段的总数量为m，建造资源总数为n。

（1）基于流水生产方式的曲面分段建造顺序分析方法 每个分段根据其制造工艺所需建造资源的类型，以及场地内部已有分段建造资源的情况进行计算。曲面分段共有m个，每个分段具有工序数量为k（k≤n），计算分段建造顺序时需遍历待安排分段工序与场地内已安排分段工序的建造资源关联关系，最差情况下，每个人需要遍历k2次，因此其复杂度为o（k2）。

（2）曲面分段图形化碰撞检测技术 设分段几何外形有a条边，每条边都要与其他在场地内分段的边的延长线进行碰撞判断，因此在最坏情况下，所有场地内分段的边都需要与待判定分段进行碰撞检测，其复杂度为o（a2）。

（3）分段场地位置分配技术 场地分配过程中需要对分段进行4次方向调整，再进行场地内碰撞检测，因此其算法复杂度仍然为o（a2）。

（4）基于虚拟流水的人力资源分配方法 人力资源分配过程与场地内的分段个数、分段工序和人员数量相关，在最坏情况下，需要遍历所有的人员以及分段的所有工序，因此其算法复杂度仍然为o（n2）。

综上所述，基于虚拟流水的曲面分段空间调度方法的算法复杂度不会超过2次多项式。

7 初步研究成果与典型应用

为验证本文提出的分布式协同生产调度技术，以上述关键技术为基础，利用Visual C++开发调度系统，以上海某船厂曲面分段建造车间为背景，并以船舶实际制造过程得到虚拟数据为依据，对上述关键技术进行验证。

空间调度系统控制界面如图7所示，该系统可根据调度人员的需要，以天或月为单位显示场地调度方案，向调度人员展示分段在制造过程中从进入场地生产到完成生产吊离场地的整体过程，辅助调度人员对场地资源的利用率和生产现状进行控制。场地内的分段根据方案的加工开始时间和结束时间吊入和离开制造场地。系统还可展示分段在生产过程中的各种加工信息。在系统后台，调度算法对分段的流水加工序列进行计算，以保证调度方案符合生产实际。

表1所示为虚拟流水生产模式下建造资源的部分调度方案，它与图1中曲面分段的空间调度方案相互关联。建造资源以班组负责人为单位流转于各个曲面分段之间，呈现出流水制造形式，在分段生产过程中实现了无空闲连接，降低了建造资源的空闲率。

表1 基于虚拟流水的建造资源调度方案（部分）

基于流水的分段制造顺序系数计算公式为

图8所示为分段基于流水生产方式优先级的生产顺序，其中优先级较大即制造系数Z较小的分段优先进入场地进行排产，保证了其制造不受场地面积的限制，同时也保证了人力资源在各分段之间能够无等待地流转。图中根据实际生产经验对分段建造系数中的权重比值分别取制造周期为wh1=0.5，人力资源均衡为wh2=0.3，场地剩余面积为wh3=0.2。其中场地面积按照单位比例缩小为900单位，实际代表的场地面积为900m2。经过计算，上述分段在采用流水式生产排布方式后，生产效率提升50%，有效地避免了分段建造过程中可能出现的窝工、待工现象，提高了除生产场地以外的人力资源利用率。

图9所示为依据基于生产实际的分段数据完成的调度方案。其中分段根据其制造优先级分别进入场地内进行位置分配，分段在进入场地后，根据当前场地的剩余面积，按照最小包络面积规则进行位置选取。图中已包含两个分段，第三个分段加入场地后，根据碰撞规则寻找场地内部不存在碰撞的位置，根据式（3）计算其包括的面积旋转分段方向，寻找在此分段面积图形下的分段位置，继续通过优化规则计算分段的包络面积，直到完成所有四个位置的旋转，最终确定具有最小包络面积的位置作为分段的场地位置。由此经过不断迭代，当所有分段都进行分配后，获得整体调度方案。

如前文所述，对空间调度算法的研究主要集中于启发式和智能优化算法。其中大部分优化算法需要对分段图形或场地进行简化处理以得到空间调度方案，由于采用较为复杂的碰撞检测方法会造成算法计算时间过长，本文提出建造资源与空间调度方案相结合的方法，在保证场地面积利用率提升的同时，提升建造资源利用率，并通过简化碰撞检测方式缩短算法的计算时间。算法结果对比如表2所示。

从表2可以看出，通过与文献［11］中应用的启发式算法和遗传算法进行对比，本文基于虚拟流水的曲面分段调度方法，在计算时间和调度结果两方面分别提升了近10%，同时该算法还支持具有复杂几何外形的分段排产和制定建造资源调度方案。表2中的空间调度算法为不进行人力资源分配调度方案排产、单纯进行分段空间调度时分段场地面积的利用率和运行时间。从表2可以看出，场地利用率低于基于流水方式的空间调度，但运行时间相对降低。

表2 算法结果对比表

在实际应用过程中，从场地利用率和生产效率两个角度，对比本系统得到的结果与船厂调度人员手工完成的调度排产结果，其中场地面积为900 m2，对3个月的生产任务进行调度规划，两者的结果如表3所示。

表3 人工与空间调度算法结果对比

由此可见，空间调度算法比调度人员按经验进行手工调度的场地利用率，尤其是生产效率有了大幅提升。人员手工调度虽然能够在短期内得到较好的调度方案，但是对于长时间的调度方案制定，仍无法考虑所有调度因素而得到分段调度方案，更加体现出空间自动调度算法的优越性和实用性。

8 结束语

本文针对曲面分段建造空间调度问题，以虚拟流水生产方式为基础，以场地资源优化分配为核心，进行了船舶曲面分段空间调度技术的理论和方法研究。对具有复杂外形轮廓的曲面分段如何在保证建造资源虚拟流水式生产的前提下充分利用场地面积的问题展开了实质性的研究，解决了船舶曲面生产调度方案在制定过程中存在的实际问题。本文的工作总结如下：

（1）提出了基于流水生产方式的分段建造序列分析技术。以曲面分段实际生产特点为依据，对分段生产制造资源进行合理分配，使其与场地内的分段建造资源负荷相关联，为制造资源在分段之间实现流水式的无空闲周转生产提供了保证。基于分段工艺制造信息抽象出分段建造顺序系数的计算方法，为确定分段建造的顺序提供了依据，为后续曲面分段空间调度方案的制定奠定了基础。

（2）提出适应不规则外形的曲面分段空间调度技术。通过对不规则轮廓排布需求的研究，形成以图形碰撞检测为核心、以最小包络面积优化规则为依据的分段场地位置分配流程，深入研究了船舶制造应用背景下的曲面图形在有限平面空间及时间范围内的布局问题，为辅助曲面分段空间调度方案的制定提供了解决途径。

（3）以不规则曲面分段时空布局为依托，以充分利用制造场地面积和场地建造资源为目标，通过对上述两项关键技术的有机组合，形成面向船舶曲面分段的空间调度方法，对不规则图形的时空布局调度进行了创新性探索。

（4）提出基于虚拟流水的人力资源分配方法。通过分析场地内分段执行过程中存在的工序空闲时间，不断调整分段中的生产人员数量，利用延长或加快分段工序制造周期的方法，实现了人力资源在固定工位分段间的虚拟流水生产形式。

下一步将重点针对曲面分段执行过程中出现的各种生产扰动，开展综合时间和空间两个维度的曲面分段调度方案动态调整技术的研究。

［1］ZHANG Zhiying，JIANG Zhibin，CHEN Qiang，et al.Research on flow-line and it's key technologies for manufacuring curved module of ship［J］.Ship Building of China，2005，46（3）：112-116（in Chinese）.［张志英，江志斌，陈 强，等.曲面分段加工的虚拟流水线生产模式及关键技术探讨［J］.中国造船，2005，46（3）：112-116.］

［2］ZHANG Zhiying，LI Chuan，LI Zhen.Spatial scheduling oriented to curved block in shipbuilding［J］.Industrial Engineering Journal，2010，13（1）：58-63（in Chinese）.［张志英，李 川，李珍.面向船体曲面分段建造的虚拟流水线生产调度［J］.工业工程，2010，13（1）：58-63.］

［3］HAN Wenmin，JI Yongsheng，YE Taofeng，et al.The research about curve block sheduling based on vitual flow style［J］.Modern Manufacturing Engineering，2012（10）：41-46，124（in Chinese）.［韩文民，季永胜，叶涛锋，等.基于虚拟流水线的船舶曲面分段建造调度研究［J］.现代制造工程，2012（10）：41-46，124.］

［4］CAO Dapeng，YANG Heng.The research about block building based on JIT［J］.Science Technology and Engineer，2010，10（19）：4876-4881（in Chinese）.［曹大鹏，杨 衡.基于JIT 船舶分段建造调度问题研究［J］.科学技术与工程，2010，10（19）：4876-4881.］

［5］ZHANG Zhiying，JIANG Zhibin.The research about vitual flow style manufacture system［J］.Journal of East China Shipbuilding Institute：Natural Science Edition，2004，18（4）：32-36（in Chinese）.［张志英，江志斌.虚拟流水线生产系统及Petri网建模技术研究［J］.华东船舶工业学院学报：自然科学版，2004，18（4）：32-36.］

［6］LEE J K，LEE K J，PARK H K，et al.Developing scheduling systems for Daewoo shipbuilding：DASproject［J］.European Journal of OperationalResearch，1997，97（2）：380-395.

［7］LEE J K.Sufficient search space for spatial expertsystems［J］.Expert System with Application，2000，19（1）：128.

［8］ZHANG Zhiying，WANG Lei，JIANG Zhibin，et al.Spatial scheduling oriented to curved block in shipbuilding［J］.Journal of Shanghai Jiaotong University，2008，42（4）：569-573（in Chinese）.［张志英，王 蕾，江志斌，等.面向船体曲面分段建造的空间调度方法［J］.上海交通大学学报，2008，42（4）：569-573.］

［9］ZHANG Zhiying，WANG Lei.Research on rule based spatial scheduling in hull curved block construction［J］.Journal of Shanghai Jiaotong University，2009，43（11）：1709-1714（in Chinese）.［张志英，王 蕾.基于规则的船体曲面分段空间调度方法［J］.上海交通大学学报，2009，43（11）：1709-1714.］

［10］RAJ P，SRIVASTAVA R K.Solving spatial scheduling problem：an analytical approach［C］／／Proceedings of the 37th International Conference on Computers and Industrial Engineering.Los Angeles，Cal.USA：Computer and Industrial Engineering，2007：1085-1094.

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

［12］ZHENG Junli，JIANG Zhibin.Block spatial scheduling modeling and application inshipbuilding［J］.International Journal of Production Research，2012，50（10）：2744-2756.

［13］VENKATARAMANAIAH S.Scheduling in cellular manufacturing systems：an heuristic approach［J］.International Journal of Production Research，2008，46（2）：429-449.

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

［15］RYU C，SHIN J G，KWON O H，et al.Development of integrated and interactive spatial planning system of assembly blocks in shipbuilding［J］.International Journal of Computer Integrated Manufacturing，2008，21（8）：911-922.

［16］STOYAN Y，CHUGAY A.Packing cylinders and rectangular parallelepipeds with distances between them into a givenregion［J］.European Journal of Operational Research，2009，197（2）：446-455.

［17］LIU Z，CHUA D K H，YEOH K W.Aggregate production planning for shipbuilding with variation-inventory tradeoffs［J］.International Journal of Production Research，DOI：10.1080／00207543.2010.527388.

［18］YAGMAHAN B，YENISEY M M.Ant colony optimization for multi-objective flow shopscheduling problem［J］.Computers and Industrial Engineering，2008，54（3）：411-420.