船舶分段涂装作业重入调度优化算法

陈云云，张志英

(同济大学 机械与能源工程学院，上海 201804)



船舶分段涂装作业重入调度优化算法

陈云云，张志英

(同济大学 机械与能源工程学院，上海 201804)

针对分段涂装过程中存在调度效率低、完工时间长等问题，本文将分段涂装作业抽象为带有时间和空间约束的批-离散机重入过程，以最小化最大完工时间为优化目标建立数学模型，构造了基于重排策略的启发式算法。通过聚类算法和基于模拟退火的组批重排策略获得不考虑空间约束的分段分批结果，利用最大接触策略实现分段的空间组批调度，提出基于最大剩余加工时间策略和遗传算法的超启发式算法进行分段的重入调度。仿真实验表明，所提出的算法可以充分利用冲砂车间的空间，得到较优的分段涂装调度计划。

分段涂装；涂装作业;时间约束；空间约束；重入调度；启发式算法； 聚类算法;优化算法

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20160624.1127.002.html

船舶制造过程包括分段组立、预舾装，分段涂装和分段搭载等工序。涂装作业处于船体生产过程的中间位置，有着承前启后的作用。前面工序由于场地、原材料供应等因素影响，延时严重；后续工序由于船坞搭载计划变更，交货期提前。这使得分段涂装作业的加工时间要求非常严格。因此，提高分段涂装作业的效率对缩短船舶制造周期有着重要的作用。分段涂装作业包括冲砂和喷涂工序。分段冲砂指的是冲砂队对砂房中的分段表面进行二次除锈。冲砂结束的分段应及时涂上底漆，防止表面氧化。分段喷涂是喷涂队对分段涂漆作业。根据船舶建造质量和工艺规划要求，分段喷涂一般要分几次进行，喷涂次数与规定的涂层厚度有关，并且各度喷涂之间要有一定的干燥时间。分段涂装调度过程不仅要考虑冲砂和喷涂阶段的时间约束，还需考虑冲砂车间和喷涂车间的空间约束及喷涂队的派遣。因此，船舶分段涂装作业可归结为带有时间和空间约束的重入调度问题。

现阶段国内外对分段涂装调度的研究较少。Cho等[1]针对分段涂装调度，设计了包含操作策略算法、分段调度算法、安排算法和分派算法的空间调度系统。在此基础上，Kwon等[2]提出了分段涂装调度的混合整数规划模型，并采用结合优先级调度规则和diagonal-fill空间调度方法的两阶段启发式算法求解。但是上述文献侧重于分段的空间调度，未考虑分段的重入喷涂和时间约束。张志英等[3-4]研究了带有时间和空间约束的分段涂装重入调度问题。但假设所有分段只重入一次，且重入之间的干燥时间均相同。这很难满足实际的分段涂装调度要求。

Su[5]证明了带有等待时间约束的两阶段单机调度过程是一个NP-Hard问题。显然，带有时间和空间约束的分段涂装重入过程是一个更为复杂的NP-Hard问题。求解此类问题的常用方法为启发式与元启发式算法。前者可在合理时间内求出较为满意的解，但易陷入局部最优解；后者通过乱数搜寻策略，提高了解的优化能力, 但由于计算效率低而不能满足复杂调度问题的需求。而超启发式算法[6]结合了这两者的优势，只需将底层算法修改便可在不同领域应用，因此近几年在图形着色[7]、课程表安排[8-9]等问题中得到了深入地研究。但在分段涂装调度领域中的应用还很少见。

基于上述分析，本文针对分段涂装作业重入调度问题，提出了以最小化最大完工时间为目标函数，带有时间和空间约束的批-离散机重入调度模型。在此基础上，构造基于重排策略的启发式算法进行求解，得到优化后的分段涂装调度方案。

1　问题描述

分段涂装作业重入调度过程如图1所示：有m个冲砂车间，v个喷涂车间及r个喷涂队。

图1　分段涂装作业重入调度过程Fig.1　Block-painting reentrant process

分段到达冲砂车间后，工人对砂房里的分段同时进行冲砂，每一个冲砂车间可等效为一台并行批处理机。砂房中能放入的分段越多，冲砂效率越高。冲砂结束后的分段移至喷涂车间，由选定的喷涂队在一定时间内进行一度喷涂。分段至少要经过2次喷涂才能结束加工，各度喷涂之间存在干燥时间下限约束。为了便于追溯和控制分段涂层的质量，一个分段的各度喷涂作业均由同一支喷涂队完成。分段喷涂作业要求在涂装房内完成，但由于船厂往往无法提供足够的涂装房。据IMO协会规范，除一度喷涂外，剩余喷涂作业可移至堆场完成。

2　模型建立

2.1模型假设

为研究方便，对分段涂装作业重入调度问题，进行以下假设：1)分段的投影形状为矩形。2)所有分段在初始时刻均可加工。3)各阶段之间有足够的缓存区；忽略分段进出各车间所需的搬运时间和其他生产准备时间。4)劳动力充足，不考虑罢工、缺勤等约束劳动力的情况。5)假定冲砂时间只与分段的投影面积有关，并事先确定。6)假定每个分段的各度喷涂时间相同，并事先确定。根据历史数据，将检查和报验时间计入喷涂时间内。7)同一分段在不同的温度下干燥时间不同。为便于估算分段的干燥时间，假定所有分段在温度25 ℃的环境下干燥。

2.2符号列表

2)参数：wti为分段i冲砂结束到一度喷涂之间的等待时间上限，h，i∈I；dtij为分段i第j道工序结束后的干燥时间下限，h，i∈I,j≥2；ptij为第i分段第j道工序的加工时间，h，i∈I，j∈J； si为分段i的投影面积，m2，i∈I； H为冲砂车间宽度，m；W为冲砂车间长度，m；sbf为第f个冲砂车间的面积，m2，f∈F；spl为第l个喷涂车间的面积，m2，l∈L；E为无穷大数。

2.3数学模型

模型的目标函数和约束条件如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

约束(2)规定每个分段的面积都小于冲砂车间的面积。约束(3)定义分段在放置过程中可正交旋转。约束(4)表示各分段在摆放过程中互不重叠。约束(5)确保每个分段只能被分派到一个批中。约束(6)规定一个冲砂车间在同一时间至多加工一批分段。约束(7)确保每批分段的投影面积之和不超过冲砂车间的面积。约束(8)限定一个批次中的分段数不超过喷涂队的数量，以保证冲砂后的分段，都能分派到不同的喷涂队。约束(9)定义了分段实际冲砂时间为批中各分段单独冲砂所需时间的最大值。约束(10)确保每批分段在冲砂过程中，一旦开始就不能中断，直到完成冲砂作业。约束(11)和(12)分别定义了分段的冲砂开始时间和结束时间要求。约束(13)规定各喷涂车间内的分段投影面积之和不能超过喷涂车间的面积。约束(14)确保一个喷涂队在同一时间至多喷涂一个分段。约束(15)规定分段各度喷涂的加工时间相同。约束(16)保证喷涂阶段，分段至少重入1次，且喷涂过程不能被中断，由同一个喷涂队完成作业。约束(17)表明分段一度喷涂必须在喷涂车间内完成。约束(18)限定了分段冲砂后的等待时间不能超过相应的等待时间上限约束。约束(19)规定了分段重入之间的等待时间必须超过相应的干燥时间下限。约束(20)和(21)表明了分段在喷涂阶段的加工顺序要求。

3　基于重排策略的启发式算法

图2　基于重排策略的启发式算法框图(BRHA)Fig.2　Heuristic algorithm frame based on ranking strategy

3.1最大接触策略

以冲砂车间左下角为坐标原点(0,0)，建立笛卡尔坐标系。其中，x、y分别为车间的长度和宽度方向。令第一个进入冲砂车间的分段左下角坐标(xi,yi)=(0,0)，后入分段置于其右方或上方。为便于确定分段的摆放位置，将已放置分段的右侧轮廓线相连接的虚线称为包络线[13](图3)，后入分段置于包络线上。定义在包络线上从垂直到水平的所有交点为可行位置P集合，如图3中的位置1、2和3。由此得到后入分段的可行位置集合如式(22)，(x, y)为后入分段左下角的坐标。

(22)

考虑到包络线越平滑，后入的分段越能充分地利用车间空间；因此，选择分段与包络线接触最大的可行位置作为分段最终放入车间的位置。由于分段可正交旋转，所以评判分段与包络线接触的量化函数PV(position value)如下所示：

(23)

图3　可行位置S(p)Fig.3　Feasible position S(p)

图4　基于最大接触策略的PV函数示意图 Fig.4　PV function based on the maximum contact strategy

3.2基于MRTS和GA的超启发式算法

超启发式算法的思想最早可追溯到1963年[14]，按规则生成机制分为选择超启发式和生成超启发式算法。其中，选择启发式算法是将启发式搜索规则进行选择组合，对于求解复杂调度问题，比一般启发式算法更具有优势。分段涂装调度需将分段派给车间和喷涂队，运用一种调度规则无法获得合适的搜索空间，因此选用超启发式算法通过不同调度规则的选择组合，能得到更为合理的分段涂装计划。选择超启发式算法分为高层算法和底层规则。高层算法是采用元启发式算法来选择底层规则的搜索策略；底层规则为具体的调度方法。从均衡喷涂队负荷的角度，研究确定了以下启发式规则作为分段派遣到各个喷涂队的方法。其中，RJk为t时喷涂队k上待加工分段Oij的集合， p为分段当前待处理工序。

1)最大剩余加工时间规则(MRT)：剩余所需加工时间越大的分段，优先安排加工，MRT的确定如式(24)。剩余加工时间相同的分段，选择剩余重入次数最多的分段优先加工。

(24)

2)最大重入次数规则(MRN)：分段剩余重入次数越多，越先加工，MRN的确定如式(25)。为了减少喷涂队由于分段干燥造成的空闲状态，当分段剩余重入次数相同时，选择剩余加工时间大的分段，优先喷涂。

(25)

3)最大平均加工时间规则(MPT)：分段的平均重入喷涂时间越大，越先加工，MPT的确定如下：

(26)

4)先到先加工规则(FIFS)：先到达喷涂队的分段，优先加工。

图5　底层规则组合方案Fig.5　Bottom rule set

根据时间属性的不同，喷涂队加工待喷涂的分段分为待一度喷涂的分段和重入喷涂的分段。前者由于存在等待时间上限约束，所以一旦喷涂队空闲，该分段将优先加工。后者则存在干燥时间下限约束。为进一步确定重入喷涂分段在喷涂队上的加工优先级，引入MRTS策略：令Oi2加工优先级为2；剩余加工时间最大的分段Oij优先级为1，其余分段加工优先级为0。若存在分段Oij既属于一度喷涂，又拥有最大剩余加工时间，则其加工优先级为2+1=3，依次类推；从而确定t时分段在喷涂队k上的加工顺序。综上所述，采用目标函数作为适应度函数，得到基于MRTS策略和GA的超启发式算法流程为：

4)执行MRTS策略，按优先级的高低加工分段，再用FIFO规则将分段分派给喷涂车间。计算各染色体的适应度函数，保存该代最佳染色体。

6)gener=gener+1；若gener

3.3BRHA算法框架

基于上述分析，得到求解分段涂装重入调度问题的BRHA算法流程如下：

1)输入起始温度Ts，结束温度Tf，冷却率β。

2)初始化：执行CACB算法、最大接触策略、超启发式算法得到分段空间分批结果Rβ，makespan和分段涂装调度方案SS。

5)若Δ<0，则Rβ=R″β，SS=SS′，转步骤7)。

7)T=β×T。若T>Tf，转步骤3)。

4　实例验证与数值分析

4.1实例验证

为了验证模型和BRHA算法的有效性，以上海某大型造船厂的涂装车间为例，利用Matlab2013a软件，在处理器为1.2 GHz，内存为4 GB的计算机上进行求解。该造船厂有3个冲砂车间，4个喷涂车间和4个喷涂队。分段在车间内摆放时要留有一定的通道空间，因此取车间面积的60%作为有效面积。分段个数30，冲砂后的等待时间为1～4 h，干燥时间为12～24 h，部分分段的涂装数据如表1所示，冲砂车间和喷涂车间的数据如表2所示。算法输入参数：初始温度Ts为运行10次BRHA所得平均最小完工时间的1.5倍，冷却速率Ts=0.97，最终温度Tf=0.1；种群规模为30，迭代次数为30，染色体交叉概率pc=0.9，变异概率pm=0.09。

运行程序，分段的空间分批结果如图6所示，据此计算冲砂车间的平面利用率(表3)。分段第12批分批结束后，只有20号分段未分派至任何批中，所以第13批中只包含一个分段，车间的平面利用率比其他批低。从表3可得到车间的平均平面利用率为70.21%(不计第13批)。因此，BRHA算法得到的分段空间分批方案，能更好地利用冲砂车间的面积。

表1　部分分段涂装数据

分段分派到喷涂队时采用的调度规则如表4所示。当喷涂车间空间不足时，完成一度喷涂的分段必须搬到堆场。表5给出了分段离开喷涂车间的时间范围。当分段最晚离开喷涂车间的时间为零时，表明该分段整个喷涂过程都在喷涂车间进行。分段的最终涂装调度计划如图7所示。从图7可得到分段涂装作业最大完工时间为214.79 h。

表2　冲砂车间和喷涂车间数据

图6　分段空间分批布置图Fig.6　Blocks spatial batching

表3　冲砂车间平面利用率

4.2数值分析

分段涂装重入调度过程需同时考虑车间和喷涂队的分派，兼具时间和空间约束，比一般的调度问题复杂，难以找到合适的下界。因此，本文从超启发式和整体算法两个方面验证算法的最优性。为了验证超启发式算法的优越性，选用HMRT、HMRN、HMPT、HFIFS这4个算法进行对比。这4个算法与BRHA算法的不同之处在于，前者分别选用调度规则中的一种完成分段到喷涂队的派遣。引入相对偏差θ来表示算法所得目标值与相对最优值的距离比值，θ越小，解的性能越好。θ由式(27)计算得到，refCmin表示对应算法所得的目标函数值。

(27)

在表6中，f2/l3/k4表示有2个冲砂车间，3个喷涂车间和4支喷涂队，其他依次类推。从表6中可看出，BRHA算法解的平均相对偏差为0.1%，而对比算法的平均相对偏差在3%～17%。因此，在不同的问题模型和分段数量下，BRHA算法性能要明显优于HMRT、HMRN、HMPT和HFIFS算法。这充分说明了引入规则选择的超启发式算法可以很好地改善调度规则集合，进一步提升BRHA算法的性能。

此外，为了验证BRHA整体算法的最优性，增加了与文献[4]HPSO算法的对比分析。在HPSO算法中，采用最大接触和MRTS策略分别进行分段空间组批和喷涂队上分段加工顺序的确定。选取100个分段，喷涂车间和冲砂车间数据与实验验证部分一致。运行程序，算法的收敛曲线如图8所示。

BRHA算法在130代左右趋于稳定，得到分段涂装结束时间为658 h；而HPSO算法在165代左右收敛，目标函数值为668 h。这表明了BRHA算法比HPSO算法提前收敛，并且得到的解更优。因此，在求解带有空间和时间约束的分段涂装作业重入调度问题中，BRHA算法比HPSO算法更具有优势。

表4　分段喷涂派遣规则

表5　分段在喷涂车间内的时间表

图7　分段涂装重入调度甘特图Fig.7　Gantt chart of block-painting reentrant scheduling

表6　BRHA与HMRN，HMPT，HFIFS的对比

图8　BRHA与HPSO算法收敛曲线Fig.8　BRHA and HPSO algorithm convergence curves

5　结论

本文研究了船舶分段涂装作业的重入调度问题，得出以下结论：

1)综合考虑分段干燥时间，重入时间及冲砂车间的平面约束，确定以最小化最大完工时间作为评价调度方案的评价指标；

2)提出了基于重排策略的启发式算法来优化分段调度方案；

3)通过不同分段数量、车间规模以及与其他算法的对比实验分析，证明该算法可以提高分段涂装作业效率，同时可为船厂制定车间级分段涂装调度方案提供有效的依据。但是本文未考虑露天堆场的空间约束。如果涂装作业的分段太多，在有限的场地和作业时间里，可能无法安排指定的工作计划，需进一步研究。

[1]CHO K K, CHUNG K H, PARK C, et al. A spatial scheduling system for block painting process in shipbuilding[J]. CIRP annals-manufacturing technology, 2001, 50(1): 339-342.

[2]KWON B, LEE G M. Spatial scheduling for large assembly blocks in shipbuilding[J]. Computers & industrial engineering, 2015, 89: 203-212.

[3]张志英, 林晨, 杨连生, 等. 面向分段涂装作业的混合流水车

间调度[J]. 上海交通大学学报, 2014, 48(3): 382-387, 393.

ZHANG Zhiying, LIN Chen, YANG Liansheng, et al. Block-painting-operation-oriented hybrid flow shop scheduling[J]. Journal of Shanghai JiaoTong University, 2014, 48(3): 382-387, 393.

[4]林晨, 张志英. 考虑运输时间窗的批-离散混合流水车间调度[J]. 计算机集成制造系统, 2014, 21(9): 2427-2434.

LIN Chen, ZHANG Zhiying. Batch-discrete hybrid flow shop scheduling with transportation in time windows[J]. Computer integrated manufacturing systems, 2014, 21(9): 2427-2434.

[5]SU L H. A hybrid two-stage flowshop with limited waiting time constraints[J]. Computers & industrial engineering, 2003, 44(3): 409-424.

[6]BURKE E K, GENDREAU M, HYDE M, et al. Hyper-heuristics: a survey of the state of the art[J]. Journal of the operational research society, 2013, 64(12): 1695-1724.

[7]ELHAG A, ÖZCAN E. A grouping hyper-heuristic framework: application on graph colouring[J]. Expert systems with applications, 2015, 42(13): 5491-5507.

[8]KALENDER M, KHEIRI A, ÖZCAN E, et al. A greedy gradient-simulated annealing selection hyper-heuristic[J]. Soft computing, 2013, 17(12): 2279-2292.

[9]AHMED L N, ÖZCAN E, KHEIRI A. Solving high school timetabling problems worldwide using selection hyper-heuristics[J]. Expert systems with applications, 2015, 42(13): 5463-5471.

[11]CHEN Huaping, DU Bing, HUANG G Q. Scheduling a batch processing machine with non-identical job sizes: a clustering perspective[J]. International journal of production research, 2011, 49(19): 5755-5778.

[12]LIN T L, HORNG S J, KAO T W, et al. An efficient job-shop scheduling algorithm based on particle swarm optimization[J]. Expert systems with applications, 2010, 37(3): 2629-2636.

[13]WEI Lijun, ZHANG Defu, CHEN Qingshan. A least wasted first heuristic algorithm for the rectangular packing problem[J]. Computers & operations research, 2009, 36(5): 1608-1614.

[14]FISHER H, THOMPSON G L. Probabilistic learning combinations of local job-shop scheduling rules[C]//MUTH J F, THOMPSON G L. Industrial Scheduling. Englewood Cliffs, New Jersey: Prentice Hall, 1963: 225-251.

本文引用格式：

陈云云，张志英. 船舶分段涂装作业重入调度优化算法[J]. 哈尔滨工程大学学报, 2016, 37(8): 1103-1110.

CHEN Yunyun，ZHANG Zhiying. Optimization algorithm for reentrant scheduling in block painting operations[J]. Journal of Harbin Engineering University, 2016, 37(8): 1103-1110.

Optimization algorithm for reentrant scheduling in block painting operations

CHEN Yunyun，ZHANG Zhiying

(School of Mechanical Engineering, Tongji University, Shanghai 201804, China)

To solve the problems associated with block painting operations, such as low efficiency and long painting time, in this study, we abstracted the reentrant process of batch-discrete machines with respect to time and spatial constraints. We also established a mathematical model to minimize the maximum makespan and proposed a heuristic algorithm based on ranking strategy. Specifically, we developed a clustering algorithm, batch-ranking strategy based on simulated annealing to obtain a block-batching result without considering spatial constraints. Then, we formulated a maximum contact strategy to achieve block spatial-batch scheduling. We addressed block reentrant scheduling using a hyper-heuristic algorithm that integrates the strategy of maximum remaining processing time with a genetic algorithm. Our simulation results indicate that the proposed algorithms can make full use of the blasting workshop and are effective in resolving the block-painting reentrant problem.

block painting; painting operation; time constraint; spatial constraint; reentrant scheduling; heuristic algorithm; clustering algorithm; optimization algorithm

2016-01-03.网络出版日期：2016-06-24.

国家自然科学基金项目(70872076);上海市科技创新行动计划(11dz1121803).

陈云云(1992- )，女，硕士研究生;

张志英(1971- )，男，副教授.

张志英，E-mail：zyzhang08@tongji.edu.cn.

10.11990/jheu.201601002

TP301.6

A

1006-7043(2016)08-1103-08