面向分段涂装作业的混合流水车间调度

Block-Painting-Operation-Oriented Hybrid Flow Shop Scheduling

基于船舶分段涂装作业,提炼出具有重入和等待时间约束的两阶段混合流水车间调度问题.其中第一阶段含多台批处理机,第二阶段含多台离散机且存在一次重入过程,两阶段间有等待时间约束.以最小化最大完工时间为优化目标建立数学模型,提出一种结合Metropolis抽样准则和变邻域搜索的混合量子粒子群优化算法,并利用多种启发式规则进行解码.实例验证和数值分析表明,所提算法是解决分段涂装调度问题的一种有效方法.

A two-stage hybrid flow shop scheduling problem with reentrant and limited waiting time con straints was presented based on block painting operations. The first stage contained several identical batc hing machines which were able to process multiple jobs simultaneously, and the second stage contained several identical discrete machines. Minimization of the makespan was used as the optimization objective to build a mathematical model. A hybrid quantum-behaved particle swarm optimization algorithm combined with Metropolis rule and variable neighborhood search was proposed. The heuristic decoding strategy was developed to generate the scheduling scheme. Application and numerical analysis indicated that the pro- posed algorithm was an effective solution to the problem of block painting scheduling.