Semidefinite Relaxations for Parallel Machine Scheduling
Skutella, Martin
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
We consider the problem of scheduling unrelated parallel machines so as to minimize the total weighted completion time of jobs.Whereas the best previously known approximation algorithms for this problem are based on LP relaxations, we give a 32–approximation algorithm that relies on a convex quadratic programming relaxation. For the special case of two machines we present a further improvement to a 1.2752–approximation; we introduce a more sophisticated semidefinite programming relaxation and apply the random hyperplane technique introduced by Goemans and Williams on for the MAXCUT problem and its refined version of Feige and Goemans. To the best of our knowledge, this is the first time that convex and semidefinite programming techniques (apart from LPs) are used in the area of scheduling.
