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(n2m) 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.