A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations

In many practical cases of flowshop environments and especially in flowline manufacturing cells, some or all jobs may not require processing on all machines. Hence, this paper focuses on the flowshop scheduling problem with missing operations. A modification of the constructive NPS-set heuristic is proposed, which generates non-permutation schedules effectively. Furthermore, a two-phase simulated annealing (SA) method is presented that specifically considers missing operations in its procedure. The modified NPS-set heuristic and the two-phase SA are tested and statistically evaluated by an extensive computational study for total flow time criteria. The results show that the modified NPS-set heuristic as well as the specific consideration of missing operations can enhance the algorithms’ performance significantly.

在诸多流水车间（flowshop）场景的实际应用中，尤其是流水线制造单元（flowline manufacturing cells）场景下，部分或全部工件可能无需在所有机器上完成加工。故此，本文聚焦于带有缺失工序的流水车间调度问题。本文提出一种改进的建设性NPS集启发式算法（constructive NPS-set heuristic），可高效生成非置换调度方案。此外，本文还提出一种两阶段模拟退火（simulated annealing, SA）算法，其求解过程专门针对缺失工序场景进行了适配设计。本文通过针对总流程时间（total flow time）指标开展的大规模仿真实验，对改进型NPS集启发式算法与两阶段SA算法进行了测试与统计学评估。实验结果表明，改进型NPS集启发式算法，以及对缺失工序的针对性考量，均可显著提升算法的整体性能。