Performance guarantees for flowshop heuristics to minimize makespan

Performance guarantees for flowshop heuristics to minimize makespan

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics
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.

Reviews

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