图力资源的船舶分段加工时空规划方法

　　摘 要：为研究考虑人力资源以及人的非理性因素的船舶分段加工时空规划调度问题，本文依据前景理论，提出了一种新的优化模型方法。首先综合考虑多个场地之间空间和人力资源负载均衡、工期以及分段延误等多个优化目标，将时间、空间和人力资源限制等作为约束条件，构建多目标优化模型，并将人的非理性心理在人力资源负载均衡中加以考虑。其次，提出了一种结合左下角填充与搜索插空填充的分段时空规划的高效算法。最后，实际和仿真运行表明该模型方法能够在数秒之内得到上百块的规划方案，充分验证了其实用性和高效性。该研究结果将为船舶分段的时空规划调度效率提升提供有效的理论和方法支持。

　　关键词：人力资源;船舶分段;时空规划;负载均衡;前景理论;非理性;多目标优化;启发式算法

　　船舶制造属于劳动密集型产业，除了占用大量的时间和空间资源外，人力资源也是不可忽视的重要因素。据了解，建造一艘 7.5 万吨级的散货船，中国需要近 100 完工时，一个年造船能力在 140 万载重吨左右的船厂，需要生产作业工人 5000 名左右。近几年，由于地理环境艰苦等因素，造船厂人员流失情况加重，给船舶制造产业带来严峻的挑战。船舶分段加工作为船舶制造产业的重要环节之一，同样受人力资源的影响较大。考虑工作区域的时间、空间和人力资源的限制，实现对船舶分段加工调度的有效管理，往往是提高造船厂生产力的关键措施。

　　然而，人力资源不同于其他设备资源，他们的主观或非理性心理会影响工作的调度安排。因此，有必要对考虑非理性人力资源的船舶分段加工时空规划调度问题进行优化研究，以提高船舶制造的生产效率。Lee 等[1]首次开始研究船舶分段加工调度问题，将船舶分段的时空规划问题运用三维装箱理论进行描述和求解。自此，船舶分段加工调度逐渐引起了诸多学者的长期关注。当前船舶分段调度的研究重点主要在于如何提高时间和空间等资源的利用效率。在时间资源上主要研究如何缩短工期[2]或降低分段的延误情况;

　　对空间资源的研究主要分为两类，单加工场地旨在提高空间利用率[4]，而对于多加工场地来说则是多场地之间的工作量均衡[5]。由于该类问题是 NP-hard[6]，对该类问题的求解主要聚焦于智能优化方法和基于优先规则的启发式构造方法。大部分研究运用禁忌搜索[7]和遗传算法[2,8-11]等智能算法来求解船舶分段调度问题。

　　遗传算法等智能优化算法的优点是可以很有效地处理多目标优化，但同时也会因为算法复杂度太高、内部规则不透明而导致无法在生产实践中展开应用。基于优先规则的船舶分段调度是当前的研究热点，多数文献综合考虑分段加工时间、分段最早开始时间、分段最迟完工时间以及分段后续加工数量等各项指标[2,5,6]作为分段排序的依据，常用的填充规则包括左下角填充规则[12]、时空相似规则[13]、对角填充规则[14]等。

　　然而，上述优先规则主要考虑未加工分段的时空特点，而没有考虑已加工完成的分段对加工空间的扩充。综上所述，当前对船舶分段加工调度问题的研究主要集中于对时间和空间资源的规划，缺少人力资源约束对船舶分段调度优化的研究，尤其缺少人的非理性因素对船舶分段调度优化的影响分析。另外，在调度优先规则上主要聚焦于未加工分段的时空特点，而没有考虑已完成分段移除后对时空规划的影响。

　　基于此，本文针对船舶分段加工多场地调度优化问题展开研究。主要创新点如下：首先，综合考虑空间资源、时间资源以及人力资源，构建船舶制造过程中的分段加工调度的多目标优化模型;其次，运用前景理论在模型目标中将人力资源的非理性心理下的主观损失有效表达出来;最后基于分段优先规则、左下角填充规则和搜索插空填充规则设计一种改进的混合启发式构造算法，对船舶分段加工调度问题进行高效快速求解。该模型方法不仅可以为现实中的船舶分段加工时空规划调度问题提供有效的辅助决策支持，也对船舶空间调度优化相关理论方法进行了有效补充。

　　1 模型

　　1.1 问题描述

　　当前船舶制造还无法完全实现智能化制造，因此分段加工过程不仅需要悬臂起重机等专业设备，还需要人工的辅助才能完成。每一个分段加工场地可以看作是一个二维空间。一般情况下，分段和加工场地的形状大多为矩形或不规则多边形，本文假设分段和加工场地形状为矩形;分段可旋转 0 度或 90 度放置。

　　本文的多场地船舶分段加工调度问题可以定义为指定各分段的加工场地、加工顺序、加工方位，使其在满足加工时间、空间和人力资源约束的前提下，达到所有加工场地的空间负载均衡偏差最小、人力资源负载均衡偏差最小、总工期最短、分段延误数量最少的优化目标。空间负载均衡偏差是指每个加工场地的单位空间承担的的工作量与平均单位空间工作量之间的差别。人力资源负载均衡偏差是指在考虑人员主观损失的前提下，每个加工场地之间单位人员任务量分配与平均值之间的差别。

　　空间和人力资源负载均衡的表示方法。工期是指最后一个分段加工完成的时刻。延误分段是指实际完工时刻晚于最迟完工时刻的分段。船舶分段加工调度问题的约束限制分别介绍如下：首先，时间约束包括：

　　1)各分段实际开始加工时刻不能早于最早开始加工时刻;2)各分段实际完工时刻不能晚于最迟完工时刻，否则认定为该分段加工出现延误;3)各分段加工过程不能出现中断。其次，空间约束包括：1)每个分段只能处于一个加工场地;2)各分段不能超出加工场地的边界;3)各分段之间在二维空间不能重叠;4)各分段不能随意放置，只能旋转 0度或 90 度;5)各分段在加工过程中不能出现移动。

　　人力资源约束是指在每个加工时段，各分段需要的工人数量不能超过该加工空间提供的工人数量。在一个矩形的加工场地中，需要调度 5 个矩形分段。 给出了各个分段的规格大小、加工时间、需要的工人数量、最早开始时刻以及最迟完工时刻。该加工空间大小为 10×10，工人组数的限制是 5。

　　分段 1 在第一天开始加工;分段 2 和分段 3 在第 2 天开始加工;由于工人数量的限制，分段 4 无法按照最早开始时刻在第 3 天开始加工，只能在第 4 天开始加工，同时由于加工场地的空间约束，分段 4 旋转之后可以放入加工场地;由于工人数量和空间的限制，分段 5 无法按照最早开始时刻在第 3 天开始加工，只能在第 5 天开始加工，实际完工时刻为第 8 天，晚于分段 5 的最迟完工时刻，因此出现延误分段。最后在第 8 天结束，所有的分段加工完毕。

　　1.2 负载均衡

　　在加工过程中，不仅要考虑空间任务量的均衡，还要考虑人力资源工作量的均衡。考虑到人在面对不同的负载差别时，会有自己的主观判断。因此本文用前景理论的若干个特征[15,16]来描述人力资源负载均衡偏差：1)人力资源的主观损失或收益是相对于参考点来说的，本文将所有场地的平均人力资源负载作为参考点;2)相对收益来说，人们对损失更敏感，本文假设：若某个场地的人力资源负载高于平均负载，则该场地的人力资源会承担损失，否则，会获得收益;3)人们对在面对损失和收益时分别会产生风险追寻和风险规避的倾向。综合以上特征，我们给出各场地的单位人员负载均衡偏差表达式。该表达式的值越小，表明各场地的人员负载越均衡。

　　1.3 模型建立

　　本文建立了一个非线性规划模型，对考虑人力资源的船舶分段加工的时空规划调度优化问题进行具体描述。模型是以左下角为原点，在加工空间上建立平面直角坐标系，利用坐标数值表示分段的放置位置。

　　约束(14)保证每个分段都不能在最早开始时间之前开始加工;约束(15)和 (16)表示如果分段在最迟完工时刻之后仍在加工，则出现了延误;约束(17)保证了在每个加工时间段，工人数都可以满足加工需求;约束(18)是为了保证每个加工时间段加工空间的面积是充足的;约束(19)和约束(20)确保每个分段在加工时不越界，其中也包含了分段的旋转情况;约束(21)和 (22)是对两端点坐标之差的具体计算规则;约束(23)是表述分段在空间上不重叠;约束(24)和 (25)保证分段在加工过程中不能移动;约束(26)-(31)对模型的决策变量进行了定义。

　　2 算法设计

　　考虑到非线性优化模型的复杂性，本文基于现实中分段加工的优先规则和搜索插空填充算法，对传统的左下角填充搜索算法进行改进，设计了改进的混合启发式构造算法。

　　2.1 算法流程

　　本文算法的具体流程，首先，计算各分段的优先度，按照优先规则对分段进行分组，并对每个分段分配场地。然后，按照优先序依次对各场地内的分段进行操作，对于每个场地内未加工完成的分段，依次在各个时间判断分段所处的状态，并在合适的加工空间摆放。直到最后，所有的分段摆放完成，算法结束。

　　2.2 分段的场地分配本文考虑所有分段的最迟完工时间和最早开始时间对它们 进行排序， 将排好序的 分段分成round(1/2)组，将每个组的分段分到每个加工场地，本文采取空间负载均衡偏差和人力资源负载均衡偏差的比重各占 50%的方式，进行场地的分段分配。本文涉及到的分段位置，均指该物分段的左下角坐标。2.3 分段放置分段的放置以天为时间单位，在移除已加工完成的分段时，需要记录下“空缺位”，为后续的分段摆放提供搜索依据。

　　(1)分段移除：若分段放入时间和加工时间之和等于当前时间，则将分段移除，即该分段加工完毕。此时该位置标记为一个“空缺位”。(2)分段填充：如果工人数还有剩余，就按照分段排序遍历所有分段，对于最早开始时间等于当前时间的分段，进行插入摆放操作：首先遍历所有“空缺位”，考虑旋转的情况下检验此分段是否可以放入。若无法放入则执行顺序摆放操作：首先确定该分段的横坐标值，然后根据重叠规则确定纵坐标值。循环执行上述操作，当所有的分段都加工完毕，则总任务完成，该时间即为总工期。

　　3 算例分析

　　本文设计了两组算例分析，进行优化模型方法的分析验证。第一组算例为来源于某船厂的实际算例[13]，第二组算例是随机产生的测试数据。实验环境为运行在 Windows 10(64 位)操作系统下的Intel(R) Core(TM)i7-4510U CPU @ 2.00GHz (8GRAM) 笔记本，并采用 MATLAB(版本 R2016a)软件编制程序。

　　当分段规模为 5 时，CPLEX 和启发式构造算法得出的结果相差不大，但是在程序运行效率上，本文的算法更占优势。当分段规模达到 25 及更大时，CPLEX 商业软件无法得到非线性规划的优化结果。而本文的算法仅在 2 秒左右就可以得到 100 多块分段的时空调度优化方案。

　　为了验证考虑人力资源以及人的非理性对模型优化结果的影响，将本文的模型方法与两种标杆方法进行对比，标杆方法 1 在分段规划时不考虑人力资源的负载均衡，标杆方法 2 是在规划时虽然考虑人力资源的负载均衡，但是忽略人的非理性心理。虽然由本文的模型方法得到的空间负载均衡值差于标杆方法 1，但是工人负载均衡偏差明显优于标杆方法 1，并且空间和工人负载均衡平均偏差也优于标杆方法 1，尤其当分段规模较大时，平均值呈现出量级上的差别。与工人负载均衡偏差类似，当分段规模较大时，工期和分段延误数量也显著优于标杆方法 1。与标杆方法 2 相比，在分段规模较大时，本文的模型方法的优势也能体现出来。

　　4 结 论

　　本文针对考虑人力资源的船舶分段时空规划调度优化问题，重点在以下三个方面取得了一定研究成果。首先，基于最小化多个场地之间的空间、人力资源负载均衡偏差、工期和分段延误数量构建多目标优化模型，其次将前景理论用于模型中人员的非理性描述，最后设计了结合分段优先规则、左下角填充规则和搜索插空填充规则的一种启发式构造算法，在 2 秒左右就可以得到满足时间、空间以及人力资源约束的所有分段时空规划方案。该研究突破了以往仅考虑船舶调度时间和空间规划的现状，设计出兼顾人力资源非理性的船舶分段时空规划模型方法。本文的研究成果可以为船舶制造过程中的分段加工时空规划调度问题的解决提供有效的辅助决策支持。未来可以聚焦不规则分段时空规划以及多劳多得的激励机制下的工人损失和收益划分等问题进一步研究。

　　参考文献:

　　[1] LEE K J, LEE J K, CHOI S Y. A spatial scheduling system andits application to shipbuilding: DAS-CURVE[J]. Expertsystems with applications, 1996, 10(3/4): 311-324.

　　[2] DIXIT V, VERMA P, RAJ P, et al. Resource and timecriticality based block spatial scheduling in a shipyard underuncertainty[J]. International journal of production research,2018, 56(22): 6993-7007.

　　[3] 马少辉, 陆春霞. 船体不规则分段的动态空间调度算法[J].运筹与管理, 2014, 23(6): 281-287.MA Shaohui, LU Chunxia. A dynamic spatial scheduling algorithmfor irregular blocks in shipbuilding[J]. Operations research andmanagement science, 2014, 23(6): 281-287.

　　[4] ZHANG Zhiying, CHEN Jie. Solving the spatial schedulingproblem: a two-stage approach[J]. International journal ofproduction research, 2012, 50(10): 2732-2743.

　　[5] 郑俊丽, 江志斌, 陈强, 等. 典型工艺和特殊布位约束下的船舶模块空间调度算法[J]. 上海交通大学学报, 2009, 43(12): 1962-1967.ZHENG Junli, JIANG Zhibin, CHEN Qiang, et al. A spatialmodule scheduling algorithm with typical constraints oftechnology and location[J]. Journal of Shanghai Jiao Tonguniversity, 2009, 43(12): 1962-1967.

　　[6] ZHENG Junli, JIANG Zhibin, CHEN Qiang, et al. Spatialscheduling algorithm minimising makespan at block assemblyshop in shipbuilding[J]. International journal of productionresearch, 2011, 49(8): 2351-2371.

　　[7] 陶宁蓉, 蒋祖华, 刘建峰. 带时间窗约束的船体分段空间调度问题[J]. 计算机集成制造系统, 2010, 16(12): 2674-2679.TAO Ningrong, JIANG Zuhua, LIU Jianfeng. Spatial schedulingproblem with time window constraint for block assembly inshipbuilding[J]. Computer integrated manufacturing systems,2010, 16(12): 2674-2679.

　　[8] TAO Ningrong, JIANG Zuhua，ZHEN Lu. Spatial schedulingand workforce assignment problem in block assembly shop ofshipbuilding [J]. Asia-pacific journal of operational research，2014，31(1): 1-19.

　　作者：胡玉真, 张首昊, 李修桥, 张耸