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

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.