Scheduling on a 2-machine flowshop subject to random breakdowns with a makespan objective function

Two-machine flowshop scheduling problems have been discussed in the literature extensively under the assumption that machines are continuously available. We address the problem of minimizing makespan in a two-machine flowshop when the machines are subject to random breakdowns. We first show that it is sufficient to consider the same sequence of the jobs on each machine. After providing an elimination criterion for minimizing makespan with probability 1, we show that under appropriate conditions Johnson's algorithm stochastically minimizes makespan.