Makespan minimization for the m-machine ordered flow shop scheduling problem

© 2019 As a subcategory of the classical flow shop scheduling problem, the ordered flow shop scheduling problem deals with the case where processing times follow a specific structure. This study addresses the m-machine n-job ordered flow shop problem with the objective of minimizing the makespan, which is known to be NP-hard. Two efficient heuristics, and one fast iterated local search algorithm are proposed. The algorithms are developed by utilizing the pyramidal-shaped property of the problem. To the best of our knowledge, there has been no benchmark instances published for the ordered flow shop scheduling problem. This study first generates three sets of benchmarks consisting of 600 instances in total, ranging from 10 to 800 jobs and 5 to 60 machines. The algorithms are tested on those instances. The outcomes demonstrate the efficiency and effectiveness of the proposed algorithms, in particular, the iterated local search algorithm in solving the ordered flow shop scheduling problem. The solutions are also compared with those of the best available algorithm for the permutation flow shop problem, and it is shown that the Iterated Local Search performs better. We also discuss the suitability of the proposed algorithms for scheduling problems with the V-shaped property