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

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.