Optimal Two-Machine Orderings in the 3 × n Flow-Shop Problem

Consider the 3 × n flow-shop problem with machines A, B, and C. By AB and BC optimum we mean optimal solutions produced by Johnson's method for the two-machine problems AB and BC, respectively. Although not every permutation that is an AB and BC optimum simultaneously is an optimal solution of the entire problem, the set P of such permutations does contain an ABC optimum whenever it is not empty. We summarize known analytical results and solution procedures for the 3 × n flow-shop problem.