Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines

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.