Experimental comparison of approximation algorithms for scheduling unrelated parallel machines

Experimental comparison of approximation algorithms for scheduling unrelated parallel machines

0.00 Avg rating0 Votes
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: ,
Keywords: programming: linear
Abstract:

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.

Reviews

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