A PTAS for minimizing the total weighted completion time on identical parallel machines

Skutella, Martin;Woeginger, Gerhard J.
(1999)

Files

dp9929
  • Open Access
  • Unknown
  • 461.09 KB
Download

Details

Authors
  • Skutella, Martin
    Author
  • Woeginger, Gerhard J.
    Author
Abstract
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(1 + sq.root 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Skutella, M., & Woeginger, G. J. (1999). A PTAS for minimizing the total weighted completion time on identical parallel machines (CORE Discussion Papers 1999/29). https://hdl.handle.net/2078.5/28800