Stochastically minimizing makespan on a three-machine flowshop

Johnson considers the deterministic three-machine flowshop problem to minimize makespan. He shows that permutation schedules are dominant, and establishes an optimal algorithm for the cases where the minimum processing time on either machine 1 or machine 3 is not smaller than the maximum processing time on machine 2. This paper considers a three-machine flowshop to minimize makespan where machines are subject to random breakdowns. It is shown that permutation schedules are dominant for the stochastic problem as well. It is also shown that Johnson's algorithm stochastically minimizes makespan if the minimum processing time on machine 1 is not smaller than the maximum processing time on machine 2. Significance: This paper addresses the three-machine flowshop scheduling problem where machines are subject to random breakdowns. Optimal solutions are obtained with respect to makespan performance measure when certain conditions are satisfied.