# On Johnson's Two-Machine Flow Shop with Random Processing Times

A set of *n* jobs is to be processed by two machines in series. Each job
requires a (known) fixed amount of processing from each machine, and there
is an infinite waiting room in front of each machine. In a classical paper,
Johnson gave a simple rule for ordering of the set of jobs to minimize the
time needed to empty the system, i.e., the makespan. This paper studies a
stochastic generalization of this problem, in which job processing times are
independent random variables. Our main result is a condition on the
processing-time distributions, of which the Johnson's rule is a special
case, that is sufficient to imply a stochastically-smaller makespan when two
adjacent jobs in a given job sequence are interchanged. We also give an
extension of our main result to job shops.