Probability in the Engineering and Informational Sciences
- Probability in the Engineering and Informational Sciences / Volume 6 / Issue 04 / October 1992, pp 513-523
- Copyright © Cambridge University Press 1992
- DOI: http://dx.doi.org/10.1017/S0269964800002709 (About DOI), Published online: 27 July 2009
Articles
On Optimal Permutation Scheduling in Stochastic Proportionate Flowshops
Michael Pinedoa1, Dequan Shawa1 and Xiuli Chaoa2
a1 Department of Industrial Engineering and Operations Research Columbia University, New York, New York 10027
a2 Division of Industrial and Management Engineering New Jersey Institute of Technology, Newark, New Jersey 07102
Abstract
Consider m machines in series with unlimited intermediate buffers and n jobs available at time zero. The processing times of job j on all m machines are equal to a random variable Xj with distribution Fj. Various cost functions are analyzed using stochastic order relationships. First, we focus on minimizing 
where cj is the weight (holding cost) and Tj the completion time of job j. We establish that if 
are in a class of distributions we define as SIFR, and 
and 
are increasing sequences of likelihood ratio-ordered and stochastic-ordered random variables, respectively, the job sequence [1, 2, … n ] is optimal among all static permutation schedules. Second, for arbitrary processing time distributions, if is an increasing sequence of likelihood ratio-ordered (hazard rate-ordered) random variables and the costs 
are nonincreasing, then a general cost function is minimized by the job sequence [1,2,…, n] in the stochastic ordering (increasing convex ordering) sense.
