Please use this identifier to cite or link to this item:
For citation please use:
Main Title: A PTAS for minimizing the total weighted completion time on identical parallel machines
Author(s): Skutella, Martin
J. Woeginger, Gerhard
Type: Research Paper
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}))/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.
Subject(s): approximation algorithm
approximation scheme
Issue Date: 1999
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1999, 628
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 245.18 kB
DownloadShow Preview
Format: Unknown | Size: 89.69 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.