کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479386 | 1446228 | 2006 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Johnson’s problem with stochastic processing times and optimal service level Johnson’s problem with stochastic processing times and optimal service level](/preview/png/479386.png)
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.
Journal: European Journal of Operational Research - Volume 169, Issue 3, 16 March 2006, Pages 751–760