On non-permutation solutions to some two machine flow shop scheduling problems

In this paper, the authors study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, they consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation schedule, and that the problem is NP-hard in the strong sense, which contradicts some known results. The tight worst-case bound for an optimal permutation solution in proportion to a global optimal solution is shown to be 3/2. An O(n) approximation algorithm with this bound is presented. Secondly, the authors consider the two machine flow shop with finite storage capacity. Again, it is shown that there may not exist an optimal solution that is a permutation schedule, and that the problem is NP-hard in the strong sense.