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.