On Pinedo's Conjecture for Scheduling in a Stochastic Flow Shop
S. Suresh, R. D. Foley, S. Elizabeth Dickey
Operations Research · 1985 · Volume 33 · Issue 5
Abstract
Pinedo has conjectured that, in a stochastic flow shop with m machines, n − 2 deterministic jobs with unit processing time, and two stochastic jobs each with mean one, the sequence minimizing the expected makespan would schedule one of the stochastic jobs first and the other last. We prove that Pinedo's conjecture is almost true: either Pinedo's sequence or a sequence with the stochastic jobs adjacent at one end of the sequence minimizes the expected makespan. Our result does not require the stochastic jobs to have an expected value of 1, nor even to be independent and identically distributed. We show that our result cannot be improved in the sense that, in some cases, one sequence is strictly optimal, and in some other cases, the other sequence is strictly optimal.
Keywords
565 distribution comparisons, 585 stochastic flow shop
Enable JavaScript for citation tools and additional paper interactions.