On Pinedo's Conjecture for Scheduling in a Stochastic Flow Shop

S. Suresh, R. D. Foley and S. Elizabeth Dickey
Additional contact information
S. Suresh: Virginia Polytechnic Institute and State University, Blacksburg, Virginia
R. D. Foley: Virginia Polytechnic Institute and State University, Blacksburg, Virginia
S. Elizabeth Dickey: Virginia Polytechnic Institute and State University, Blacksburg, Virginia

Operations Research, 1985, vol. 33, issue 5, 1146-1153

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 (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.5.1146 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:33:y:1985:i:5:p:1146-1153

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().