A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations
针对实际生产中某些工序可能缺失的流水车间调度问题，改进了构造性NPS-set启发式算法，并提出一种两阶段模拟退火方法，通过大量实验证明其能有效优化总流程时间。
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.