Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479393 | European Journal of Operational Research | 2006 | 8 Pages |
Abstract
This paper reviews the known worst-case ratios and absolute performance guarantees of various flowshop heuristics to minimize makespan. The absolute and worst-case performance ratio bounds are compared using probabilistic analysis. The best absolute performance bound is shown to outperform the tightest worst-case ratio bound with 99% probability when a certain minimum number of jobs is present. Thus, probabilistic analysis may provide a bridge between the absolute and worst-case performance guarantees of heuristic algorithms.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Jatinder N.D. Gupta, Christos Koulamas, George J. Kyparisis,