Scheduling algorithms for multi-stage flow shops with reworks under overlapped queue time limits
研究了多阶段流水车间中，当工件在任意两阶段间的排队时间超过上限时需返工的问题，目标是极小化最大完工时间。提出了混合整数规划模型和变邻域搜索算法，并扩展为通用变邻域搜索算法，实验表明后者显著优于前者。
This study addresses a multi-stage flow shop scheduling problem in which a job is reworked when its queue time between two arbitrary stages exceeds an upper limit. The problem is to determine the start times of jobs and rework setups/operations if incurred for the objective of minimising makespan. As an extension of the previous studies, multiple overlapped queue time limits are considered, i.e. some in-between stages of queue time limits for a job are overlapped. A mixed integer programming model is developed and its performance is reported for small-sized test instances. Then, due to the limited applications of optimal solution approaches, a variable neighbourhood search (VNS) algorithm is proposed that generates an initial solution and improves it using a shaking and a local search improvement methods. In addition, it is extended to the general variable neighbourhood search (GVNS) algorithms with variable neighbourhood descent (VND) methods. Computational results show that the GVNS algorithms outperform the VNS algorithm significantly and also give near optimal solutions for small-sized test instances within a reasonable amount of computation times.