Johnson's problem with stochastic processing times and optimal service level

Johnson's problem with stochastic processing times and optimal service level

0.00 Avg rating0 Votes
Article ID: iaor2007147
Country: Netherlands
Volume: 169
Issue: 3
Start Page Number: 751
End Page Number: 760
Publication Date: Mar 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: stochastic processes, heuristics
Abstract:

Theoretical results about Johnson's problem with stochastic processing times are few. In general, just finding the expected makespan of a given sequence is already difficult, even for discrete processing time distributions. Furthermore, to obtain optimal service level we need to compute the entire distribution of the makespan. Therefore the use of heuristics and simulation is justified. We show that pursuing the minimal expected makespan by two heuristics is empirically effective for obtaining excellent overall distributions. The first is to use Johnson's rule on the means. The second is based on pair-switching and converges to some known stochastically optimal solutions when they apply. We show that the first heuristic is asymptotically optimal under mild conditions. We also investigate the effect of sequencing on the makespan variance.

Reviews

Required fields are marked *. Your email address will not be published.