陶宁蓉，蒋祖华，刘建峰，孙晓军，朱玉龙，李军涛

(1. 上海海洋大学工程学院，上海 201306; 2. 上海交通大学机械与动力工程学院，上海 200240；3. 高新船舶与深海开发装备协同创新中心，上海 200240; 4. 上海外高桥造船有限公司，上海 200137)

考虑工艺流程的船体分段多堆场调度问题研究

陶宁蓉1，蒋祖华2,3，刘建峰4，孙晓军4，朱玉龙4，李军涛1

(1. 上海海洋大学工程学院，上海 201306; 2. 上海交通大学机械与动力工程学院，上海 200240；3. 高新船舶与深海开发装备协同创新中心，上海 200240; 4. 上海外高桥造船有限公司，上海 200137)

为了有效解决在船舶建造过程中物流拥堵的问题，综合考虑分段建造工艺流程、分段大小和堆场布局，以最小分段移动度为目标，提出基于工艺流程的多堆场船体分段调度方法，并针对调度过程中出现的阻挡分段提出堆位调整算法。对上海某造船厂分段物流进行的实际验证表明，本方法可获得较优化的调度方案，可有效提高作业效率。

物流系统管理；分段堆场；分段工艺流程；分段移动度；阻挡分段

在现代造船模式下，船舶建造以中间产品“分段”作为基本作业单元，分段在组立车间成型后脱胎，需要经过预舾装、喷砂、涂装等工艺，最后到船坞进行总组搭载。由于天气、检验等不确定因素，分段在工序之间的流动并非无缝连接，堆场作为分段临时存放的场所，用以缓解对生产车间资源的需求。然而，由于分段质量大、体积大，移动缓慢且成本高，分段物流已成为船厂非常重视的活动之一。目前，因为调度不合理和管理缺乏，堆场上分段堆放无序，造成分段进出堆场移动困难，导致过多阻挡分段，严重影响生产的进度。因此，优化分段堆场调度是船厂亟需解决的问题。

船体分段堆场调度属于二维平面调度问题，但除了要考虑分段的时间约束和空间约束，还需要考虑分段在运输过程中对移动路径上的空间需求[1]。目前，国内外文献主要是针对堆位分配进行研究，以减少分段进出场时引起的阻挡分段临时移动。文献[2]首次研究了分段堆场调度对提高堆场利用率及减少无效劳动的重要意义，文献[3—5]将分段堆场优化调度过程建立数学模型，研究了进场分段堆位选择策略和阻挡分段临时移动策略。文献[6]将BP神经网络用于预测周期内进出场分段的数量。文献[7—8]考虑了分段形状和尺寸的差异性对场地利用率的影响。此外，文献[9]研究了分段进场时的堆位选择评价函数，并提出针对堆位选择的禁忌搜索算法，文献[10]提出平板车在堆场中可以直角转弯以选择阻挡分段更少的路径，并用最短路算法求解小规模堆场调度；文献[11]在此基础上考虑了分段进场时间不确定和路径变化对堆场调度的影响，另外，文献[12—13]将分段在多车间的调度转换成并行机调度问题，文献[14]结合运输能力限制和堆场面积约束，提出了分段两阶段多车间调度模型，文献[15]针对总组平台提出分段调度模型。

现有文献大多针对单个堆场上的调度问题进行分析和求解，没有考虑实际应用中多堆场的并行调度，而针对多车间调度的研究也没有和分段堆场上堆位调度问题结合起来考虑。另外，没有结合分段的实际尺寸考虑同一堆位上放置多个小分段的情况。针对以上问题，本文考虑了分段尺寸大小和分段堆位偏好，提出面向工艺流程的多堆场调度模型，分析基于网格的多分段并存的移动度表达和堆位搜索方法，并针对阻挡分段提出堆位调整算法，实现阻挡分段再调度，降低当前调整对后续任务的影响，最后结合船厂的实际数据对模型进行了实例验证。

1 问题描述

图1左侧为一船厂内分段堆场和各个工艺阶段的建造车间的分布示例。堆场上堆位采用网格式划分，由于厂区布局的限制，分段堆场的尺寸和形状不同，图1右侧为5×8的分段堆场。

图1 船厂堆场布局示例Fig.1 Example of block stockyard in shipyards

在滚动作业计划下，获取当期各堆场上的堆存信息，根据当前调度期内的分段调度需求，为各分段选择合适的堆场并为其在堆场中分配合理的堆位，同时基于分段的进出场移动路径和堆场布局，确定阻挡方段的移动策略，使得分段移动度最小。

调度周期内执行分段任务所产生的总移动度最小的目标函数如下：

Minimize

(1)

式(1)的约束条件如下：

1≤ti≤T,

(2)

(3)

(4)

(5)

(6)

(7)

式(2)约束任务分段的执行时间在调度周期内；式(3)约束同一时间只执行1个任务；式(4)约束堆位上分段面积的总和小于堆位面积；式(5)约束1个分段只能放置在1个堆位上；式(6)约束分段进出堆场的路径为移动度最小路径；式(7)保证分段优先放在与分段类型对应的偏好堆位。

2 求解算法

2.1 基于工艺流程的多堆场堆位调度方法

船舶生产是典型的拉式生产方式，基于任务分解的思想[16]，根据船舶工艺流程，分段的流向服从脱胎—预舾装—冲砂—涂装—总组，结合分段的搭载顺序和各工艺流程的标准周期，确定分段在当前调度周期内的作业时间需求，如图2所示。

图2 基于工艺流程的多堆场调度方法Fig.2 Multi-stockyard scheduling method based on technological process

2.2 分段移动度最小的堆位搜索算法

1)分段移动度分析

图3对应图1的堆场信息。

图3 分段堆场的数字化表达Fig.3 Mathematical express of block stockyard

圆圈表示堆位，有标号的圆圈表示该堆位上有分段，圆圈左下方的椭圆表示堆位编号，道路的编号为0，圆圈内堆位信息分2行：第1行数字代表分段编号，第2行以“|”为分隔，分别代表分段的进场时间和出场时间，其中“-1”表示当前调度周期前该分段已在场。如14(1|4)表示14号分段是当前调度周期的第1天入场、第4天出场。

在选择分段进、出场路径时，将堆位看作节点，节点状态“2”，“1”和“0”分别表示堆位上分段的个数，相邻堆位由带权重的边连接，权重的大小与移动度对应。设遇到1个阻挡分段和1个空堆位的移动度分别为α和β。因为移动阻挡分段的成本很大，α取值应远大于β，如取α=1，β=0.001。考虑到1个堆位上放置2个分段的情况，将与状态为“2”和“1”的堆位相邻边的权重定为1和0.5，如图4所示。

图4 堆位节点距离图
Fig.4 Distance between stockyard nodes

2)堆位搜索流程

根据船厂堆场上每个堆位对不同工艺流程的分段偏好，该流程有偏好地选择放置堆位。结合分段的尺寸，将可放置堆位分为两大类，即空堆位集C1和非空堆位集C2。在得到候选堆位集C1和C2后，首先在堆位候选集C2中选择出场时间与任务分段出场时间一致的堆位，通过Dijkstra算法计算分段从起始位置到达候选堆位的最短路径并计算移动度；在候选堆位集C1中计算分段从起始位置到达候选堆位的最短路径并计算移动度，具体流程见图5。

2.3 阻挡分段移动算法

图6为分段移动路径上遇到阻挡分段时的调度算法。阻挡分段在正常的任务分段的移动任务执行过程中产生，其移动为正常分段移动任务的衍生任务，会增加额外的成本。对于已经产生的阻挡分段，移动的目的首先要不再产生新的阻挡分段，同时进一步改善堆场布局，降低后续分段移动的成本。

3 算法应用

本文算法结合上海某大型船厂分段堆场调度的实际情况予以实现。由于涉及多个堆场的若干个堆位和分段，故仅列举部分数据：表1为堆场堆位的初始状态，即堆场上已有分段及其预计出场时间；表2为当前调度任务信息；表3为各堆场堆位尺寸、空间位置、对应的工艺阶段偏好，堆位ID的编码采用字母和数字组合的方式，如“P7104”。参数α=1， β=0.001。

图5 分段堆位搜索流程Fig.5 Searching flow for block storage location

图6 阻挡分段移动策略框架Fig.6 Frame of moving strategy for obstructive blocks

分段ID堆位ID预计出场时间分段ID堆位ID预计出场时间110P7102第3天103P6416第3天100P6403第1天104P6412第4天101P6404第1天105P6413第5天102P6408第2天106P6414第1天………………

表2 分段调度任务列表

表3 各分段堆场上堆位的信息

通过本文算法确定的分段调度结果如表4所示，对于每一条分段移动任务，算法给出其在堆场内移动的路径。所谓堆场内的移动路径，是由一个个相邻的堆位序列来表示的，其中每一条路径的第1个位置点为该分段的初始停放位置，而最后一个位置点则为该分段的终止停放位置。如果位置在堆场上，则会给出对应的堆场变化；如位置在某个工艺流程的车间，则给出对应的车间名字即可。“-R-”表示该分段移动任务要求分段先从初始堆场或车间出来，再进入另一个堆场或车间，“-R-”前后的路径分别表示该分段出堆场和进堆场的路径。

在实际生产中，分段堆场调度主要是依靠调度人员的经验，目前只能做到每半天做1次调度计划，而且还得安排人员随时跟进现场实际情况进行调整，需要匹配大量的人力、物力和时间成本。利用本文所研究的方法，可以对分段在多堆场/车间之间以及在堆场内部的移动进行统一规划，以获得较优的调度方案，结合分段的工艺阶段和分段尺寸，充分利用堆场资源，提高作业效率，并且可以实现1周以上的滚动作业计划，大大提高实际作业的计划性和可实施性。

表4 多堆场分段调度方案

4 结 语

基于实际情况，对船舶建造过程中的分段堆场调度进行了研究，考虑了分段所处工艺阶段以及多堆场中各堆位相对于分段工艺阶段的偏好，结合一个堆位可放置超过一个小分段以提高空间利用率的需求，提出面向建造工艺流程的多堆场调度模型，分析了基于网格的多分段并存的移动度表达和堆位搜索方法，并针对阻挡分段提出堆位调整算法。后期研究将考虑采用智能算法对堆位选择与阻挡分段调整进一步优化，以获得更好的结果。此外，实际情况中的不确定因素、对未来堆场作业的预见性也是需要进一步研究的内容。

[1] 陶宁蓉. 船舶分段建造过程中的资源调度优化研究[D]. 上海：上海交通大学, 2013. TAO Ningrong. Research on Resource Scheduling Problems during Ship Block Assembly Process[D]. Shanghai: Shanghai Jiao Tong University, 2013.

[2] PARK C, SEO J, KIM J. Assembly block storage location assignment at a shipyard: A case of hyundai heavy industries[J]. Production Planning & Control, 2007, 18(3): 180-189.

[3] PARK C, SEO J. Assembly block storage location assignment problem: Revisited[J]. Production Planning & Control, 2009, 20(3): 216-226.

[4] PARK C, SEO J. Mathematical modeling and solving procedure of the planar storage location assignment problem[J]. Computers & Industrial Engineering, 2009, 57(3):1062-1071.

[5] PARK C, SEO J. Comparing heuristic algorithms of the planar storage location assignment problem[J]. Transportation Research Part E Logistics & Transportation Review, 2010, 46(1):171-185.

[6] 周键, 曹瑞霞, 汪雄. 分段堆场预测调度研究[J].计算机工程与应用, 2013, 49(23): 221-227. ZHOU Jian, CAO Ruixia, WANG Xiong. Shipbuilding yards predictable scheduling approach[J]. Computer Engineering and Applications, 2013, 49(23): 221-227.

[7] 张志英, 杨克开, 于瑾维. 面向船体分段建造的二维不规则空间调度方法[J].上海交通大学学报, 2012, 46(4): 651-656. ZHANG Zhiying, YANG Kekai, YU Jinwei. Two-dimensional irregular spatial scheduling method for hull block construction in shipbuilding[J]. Journal of Shanghai Jiao Tong University, 2012, 46(4): 651-656.

[8] 陆春霞. 船体不规则分段的动态空间调度及场地堆放问题研究[D]. 镇江：江苏科技大学, 2013. LU Chunxia. Research on Irregular Block Dynamic Spatial Scheduling and Stacking Problem in Shipbuilding Industry[D]. Zhenjiang: Jiangsu University of Science and Technology, 2013.

[9] TAO Ningrong, JIANG Zuhua, QU Shipeng. Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards[J]. International Journal of Production Research, 2013, 51(14): 4289-4301.

[10]张志英, 申钢, 刘祥瑞. 基于最短路算法的船舶分段堆场调度[J]. 计算机集成制造系统, 2012, 18(9): 1982-1990. ZHANG Zhiying, SHEN Gang, LIU Xiangrui. Block storage yard scheduling of shipbuilding based on shortest-path algorithm[J]. Computer Integrated Manufacturing Systems, 2012, 18(9): 1982-1990.

[11]陈凯, 蒋祖华, 刘建峰, 等. 带有进场时间窗的船舶分段堆场调度研究[J]. 上海交通大学学报, 2016, 50(9): 1390-1398. CHEN Kai, JIANG Zuhua, LIU Jianfeng, et al. Shipbuilding yard scheduling with block inbound time window[J]. Journal of Shanghai Jiao Tong University, 2016, 50(9): 1390-1398.

[12]ROH M, CHA J. A block transportation scheduling system considering a minimization of travel distance without loading of and interference between multiple transporters[J]. International Journal of Production Research, 2011, 49(11): 3231-3250.

[13]PARK C, SEO J. A GRASP approach to transporter scheduling and routing at a shipyard[J]. Computers & Industrial Engineering, 2012(63): 390-399.

[14]代乙君, 张志英, 王维泽. 运输能力有限的分段两阶段多车间调度问题[J]. 计算机工程与应用, 2016, 52(7): 222-235. DAI Yijun, ZHANG Zhiying, WANG Weize. Block two-stage and multi-workshop scheduling with transportation consideration[J]. Computer Engineering and Applications, 2016, 52(7): 222-235.

[15]李敬花, 樊付见, 余峰. 求解船体分段堆场调度问题的改进遗传算法[J]. 计算机集成制造系统, 2012, 18(12): 2674-2682. LI Jinghua, FAN Fujian, YU Feng. Improved genetic algorithm for ship block yard scheduling problem[J]. Computer Integrated Manufacturing Systems, 2012, 18(12): 2674-2682.

[16]魏妮妮,宋翌. 基于任务分解的时间均衡度算法[J].河北科技大学学报, 2013, 34(6): 559-564. WEI Nini, SONG Yi. A time-balancing scheduling algorithm based on task decomposition[J]. Journal of Hebei University of Science and Technology, 2013, 34(6): 559-564.

Multi-stockyard scheduling problem considering technological process of hull blocks

TAO Ningrong1， JIANG Zuhua2,3， LIU Jianfeng4， SUN Xiaojun4， ZHU Yulong4， LI Juntao1

(1.College of Engineering, Shanghai Ocean University, Shanghai 201306, China; 2.School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 3. Collaborative Innovation Center for Advanced Ship and Deep-Sea Exploration, Shanghai 200240, China; 4. Shanghai Waigaoqiao Shipbuilding Company Limited, Shanghai 200137, China)

In order to effectively solve the current status of logistics congestion in shipbuilding process, the technological process of blocks, block size and block stockyard layout are considered. With the objective to minimize block move degree, a multi-stockyard scheduling algorithm based on technological process of blocks is proposed, and an adjustment algorithm for obstructive blocks is given. The application of the method in a shipbuilding company in Shanghai shows that the method can obtain optimal scheduling scheme and improve operation efficiency.

logistics systems management; block stockyard; technological process of blocks; block move degree; obstructive block

1008-1534(2017)01-0012-06

2016-10-31;

2016-11-21；责任编辑：冯 民

国家自然科学基金(71501125)；上海高校青年教师培养资助计划(ZZHY14031)；工业和信息化部项目(工信部联装[2014]507号)

陶宁蓉(1983—)，女，江苏盐城人，讲师，博士，主要从事生产计划、物流管理、调度优化等方面的研究。

E-mail: nrtao@shou.edu.cn

TP391;U673

A

10.7535/hbgykj.2017yx01003

陶宁蓉，蒋祖华，刘建峰,等.考虑工艺流程的船体分段多堆场调度问题研究[J].河北工业科技,2017,34(1):12-17. TAO Ningrong，JIANG Zuhua，LIU Jianfeng,et al.Multi-stockyard scheduling problem considering technological process of hull blocks[J].Hebei Journal of Industrial Science and Technology,2017,34(1):12-17.