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 dis tribution is also given analytically when the distribution of jobs among th e two types is binomial. These distributions show a great asymmetry that co nfirms most of experimental observations that are proposed in the literatur e. These results are obtained by an analogy between this particular schedul ing 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.