Fast heuristics for minimizing the makespan in non-permutation flow shops

We introduce a new permutation representation for non-permutation schedules, and show how the acceleration technique of Taillard can be extended to it. We propose three new heuristics for the non permutation flow shop scheduling problem with makespan minimization: a constructive heuristic with the same time complexity as the well-known NEH heuristic, a non-permutation insertion local search with a time complexity O(n(2)m) for evaluating a neighbourhood on n jobs and m machines, the same as for the permutation insertion local search, and a reduced-neighbourhood best-improvement non permutation local search with a time complexity of O(nm) per neighbourhood. These heuristics are combined into iterated greedy algorithms for the permutation and non-permutation flow shop scheduling problem. In extensive computational experiments we find that our iterated greedy algorithms produce better non-permutation schedules than other methods for the permutation and non-permutation flow shop scheduling problem, in the same computational time. (C) 2018 Elsevier Ltd. All rights reserved.