Performance guarantees for flowshop heuristics to minimize makespan |
| |
| Affiliation: | 1. Department of Accounting and Information Systems, University of Alabama in Huntsville, College of Administrative Science, Huntsville, AL 35899, USA;2. Department of Decision Sciences and Information Systems, Florida International University, Miami, FL 33199, USA;1. School of Mathematics and Computer Science, Anhui Normal University, Wuhu 241003, Anhui, China;2. Institute of Mathematical Science, Nanjing Normal University, Nanjing 210046, Jiangsu, China |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
