Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops

• We propose a constructive heuristic for non-permutation flow shop scheduling.
• The constructive heuristic finds good makespans in a short time.
• We further propose a local search heuristic for the problem.
• The local search is significantly better than current non-permutation heuristics.
• The local search is competitive with and often improves best permutation schedules.
• We also find that non-permutation schedules reduce buffer requirements.

We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules.