Exact distribution of the makespan in a two machines flow shop with two kinds of jobs

This paper deals with the no-delay permutation flow shop with two machines and two kinds of jobs. In this case, the distribution of the makespan for a randomly chosen sequence can be computed analytically with special numbers N(n, p, i) that are extensions of the binomial numbers. The makespan's distribution is also given analytically when the distribution of jobs among the two types is binomial. These distributions show a great asymmetry that confirms most of experimental observations that are proposed in the literature. These results are obtained by an analogy between this particular scheduling problem and the lattice path counting problem (random walk) studied for more than a century in theoretical combinatory. (C) 2001 Elsevier Science B.V. All rights reserved.