Loading…
A PTAS for minimizing the total weighted completion time on identical parallel machines
Skutella, Martin; J. Woeginger, Gerhard
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
We consider the problem of scheduling a set of n jobs on m identical parallel machines so as to minimize the weighted sum of job completion times. This problem is NP-hard in the strong sense. The best approximation result known so far was a ((1+ 2}))/2-approximation algorithm that has been derived by Kawaguchi and Kyan back in 1986. The contribution of this paper is a polynomial time approximation scheme for this setting, which settles a problem that was open for a long time. Moreover, our result constitutes the first known approximation scheme for a strongly NP-hard scheduling problem with minsum objective.
