Premium
A note on minimizing the expected makespan in flowshops subject to breakdowns
Author(s) -
Du Charles,
Pinedo Michael
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199512)42:8<1251::aid-nav3220420809>3.0.co;2-q
Subject(s) - job shop scheduling , sequence (biology) , generalization , computer science , mathematical optimization , schedule , random variable , process (computing) , subject (documents) , algorithm , artificial intelligence , mathematics , statistics , chemistry , mathematical analysis , biochemistry , library science , operating system
Abstract 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.