A note on minimizing the expected makespan in flowshops subject to breakdowns

Consider a two machine flow shop and n jobs. The processing time of job j on machine i is equal to the random variable X ij One of the two machines is subject to breakdown and repair. The objective is to find the schedule that minimizes the expected makespan. Two results are shown. First, ifP(X 2j ≧ X 1j ) = 1 for all j and the random variables X 11 , X 12 ,…, X 1n are likelihood ratio ordered, then the SEPT sequence minimizes the expected makespan when machine 2 is subject to an arbitrary breakdown process; if P(X 1j ≧X 2j ) = 1 and X 21 , X 22 ,….,X 2n are likelihood ratio ordered, then the LEPT sequence minimizes the expected makespan when machine 1 is subject to an arbitrary breakdown process. A generalization is presented for flow shops with m machines. Second, consider the case where X 1j and X 2j are i.i.d. exponentially distributed with rate λ j . The SEPT sequence minimizes the expected makespan when machine 2 is subject to an arbitrary breakdown process and the LEPT sequence is optimal when machine 1 is subject to an arbitrary breakdown process. © 1995 John Wiley & Sons, Inc.