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.