A Probabilistic Analysis of Two-Machine Flowshops

We study a two-machine flowshop in which all processing times are independently and identically distributed, with values known to the scheduler. We are able to describe in detail the expected behavior of the flowshop under optimal and heuristic schedules. Our results suggest that minimizing makespan might be a superfluous objective: random schedules are easier to construct and require significantly less intermediate storage between the machines; moreover, they are known to be asymptotically optimal.