Abstract: To improve the efficiency of block production in shipbuilding,a two-stage hybrid flow shop scheduling problem with transportation in time windows driven from block-painting operations was researched.The first stage contained several identical batch processors,and the second stage contained several identical discrete processors.The batch processor could process several jobs simultaneously so that all jobs of the same batch were started and completed together.Limited waiting time and transportation capacity constraints were existed between these two stages,and the transportation process between two stages must occur in the specific time windows.For the objective of minimizing the makespan,a mathematical model by considering the block-layout in blasting cells was established,and a Differential Evolution (DE) algorithm combined with multiple heuristic rules was proposed.Application and numerical analysis showed that the proposed algorithm could obtain a satisfying near-optimal solution to solve the block-painting scheduling problem within an acceptable computational time.

Key words: block painting, hybrid flow shop scheduling, transportation, batch processors, discrete processors, differential evolution

摘要： 为提高船舶分段生产效率,研究从分段涂装作业中提炼出的考虑运输时间窗的两阶段混合流水车间调度问题。其中第一阶段含多台批处理机、第二阶段含多台离散机。批处理机能同时处理多个工件,因而同一批次的工件在批处理阶段具有相同的开始作业和完成作业时间。两阶段之间存在有限等待时间和运输能力约束,并且阶段间的运输过程只能发生在特定运输时间窗内。以最小化最大完工时间为优化目标,同时考虑分段在冲砂车间的排布建立数学模型,提出一种混合多种启发式规则的差分进化算法。实例验证和数值分析表明,所提算法能在可接受运行时间内获得较满意的近优解,为分段涂装调度问题提供有效的解决方案。

关键词: 分段涂装, 混合流水车间调度, 运输, 批处理机, 离散机, 差分进化