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 li terature extensively under the assumption that machines are continuous ly available. We address the problem of minimizing makespan in a two-m achine 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 mi nimizing makespan with probability 1, we show that under appropriate c onditions Johnson's algorithm stochastically minimizes makespan.