IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/1999029.html
   My bibliography  Save this paper

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

Author

Listed:
  • SKUTELLA, Martin

    (Technische Universität Berlin, Fachbereich Mathematik, MA 6-1; StraBe des 17. Juni 136, D-10623 Berlin, Germany)

  • WOEGINGER, Gerhard J.

    (Technische Universität Graz, Institut für Mathematik, Steyrergasse 30, A 8010 Graz, Austria)

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.

Suggested Citation

  • SKUTELLA, Martin & WOEGINGER, Gerhard J., 1999. "A PTAS for minimizing the total weighted completion time on identical parallel machines," LIDAM Discussion Papers CORE 1999029, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:1999029
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp1999.html
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:1999029. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.