Article ID: | iaor20032799 |
Country: | United States |
Volume: | 14 |
Issue: | 2 |
Start Page Number: | 175 |
End Page Number: | 189 |
Publication Date: | Apr 2002 |
Journal: | INFORMS Journal On Computing |
Authors: | Hurkens Cor, Vredeveld Tjark |
Keywords: | programming: linear |
This paper presents an empirical comparison of polynomial-time approximation algorithms and local search heuristics for the problem of minimizing total weighted completion time on unrelated parallel machines. Algorithms with a worst-case performance guarantee are based on rounding a fractional solution to an LP-relaxation or to a convex quadratic-programming relaxation. We also investigate dominance relations among the lower bounds resulting from these relaxations.