Skutella, MartinJ. Woeginger, Gerhard2021-12-172021-12-1719992197-8085https://depositonce.tu-berlin.de/handle/11303/15943http://dx.doi.org/10.14279/depositonce-14716We 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.en510 Mathematikapproximation algorithmapproximation schemeschedulingResearch Paper