Stochastic flow shop scheduling

Abstract

In this dissertation we present new results for minimizing the makespan in a flow shop with zero storage between machines. Makespan is the total length of time required to process a set of jobs. We consider m machines and n jobs with random processing times. Since there is no intermediate storage between machines, a job that has finished processing at one machine may have to stay on that machine until the next machine is free. Our goal is to select a schedule that will minimize the makespan.

Our results require various stochastic orderings of the processing time distributions. Some orderings minimize the expected makespan, and some stronger results stochastically minimize the makespan. The optimum sequence of these latter cases not only minimizes the expected makespan but also maximizes the probability of completing a set of jobs by time t for any t.

The last result is concerned with scheduling jobs on two identical parallel machines. The jobs are subjected to some intree precedence constraints. We resolve a conjecture that appeared in Pinedo and Weiss (1985) and give conditions under which the conjecture is true and give examples to prove that the conjecture is false in general.