Article ID: | iaor2007154 |
Country: | Netherlands |
Volume: | 169 |
Issue: | 3 |
Start Page Number: | 865 |
End Page Number: | 872 |
Publication Date: | Mar 2006 |
Journal: | European Journal of Operational Research |
Authors: | Gupta Jatinder N.D., Koulamas Christos, Kyparisis George J. |
Keywords: | heuristics |
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.