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

Martin Skutella () and Gerhard J. Woeginger ()
Additional contact information
Martin Skutella: Technische Universität Berlin, Fachbereich Mathematik, MA 6-1; StraBe des 17. Juni 136, D-10623 Berlin, Germany
Gerhard J. Woeginger: Technische Universität Graz, Institut für Mathematik, Steyrergasse 30, A 8010 Graz, Austria

No 1999029, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 + √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.

Keywords: scheduling theory; approximation algorithm; approximation scheme; worst-case ratio; combinatorial optimization. (search for similar items in EconPapers)
Date: 1999-05-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1999.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1999029

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().