Abstract: To solve the rescheduling problem for a random or an anticipated machine disruption in proportional two-machine no-wait flow shop, a disruption management method is proposed that considering both the original objective(min. makespan)and the disruption repairing objective(min.summation of delay time). Based on the shortest processing time(SPT)rule optimal analyzing, it is proved that the right shift original schedule is optimal for the post-disruption management problem. And a predictive disruption management model is formulated based on SPT rule. By combining the ideal point-based multi-objective approaching policy with the discrete quantum-behaved particle swarm optimization and local search mechanism, a heuristic algorithm is proposed. The numerical experiments show that the model and algorithm are effective.

Key words: operations research, rescheduling, disruption management, SPT rule, quantum-behaved particle swarm optimization, no-wait flow shop

摘要： 针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。

关键词: 运筹学, 重调度, 干扰管理, SPT规则, 量子微粒群优化, 无等待流水线