Scheduling of a two-machine flowshop with availability constraints on the first machine

We treat the problem of scheduling n immediately available jobs in a flowshop composed of two machines in series with the objective of minimizing the makespan, when it is known that there shall be an interruption in machine availability on the first machine. We also consider two types of processing regimes: “stop resume” and “stop restart”. We present efficient dynamic program models for both regimes. But we focus on the performance of the Johnson rule as a heuristic. We establish the conditions under which it yields the optimum, and demonstrate that in other cases its performance is bounded by 2.