Thumbnail Image

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.