Inhalt des Dokuments
Preprint 628-1999
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- A PTAS for minimizing the total weighted completion time on identical parallel machines
- Authors
- Martin Skutella and Gerhard J. Woeginger
- Publication
- Mathematics of Operations Research, 25(1), 63-75, 2000. An extended abstract appeared in the proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC'99), pp. 400-407.
- Classification
-
MSC: primary: 90C27 Combinatorial optimization secondary: 68Q25 Analysis of algorithms and problem complexity 90B35 Scheduling theory, deterministic 68M20 Performance evaluation; queueing; scheduling - Keywords
-
approximation algorithm, approximation scheme, scheduling
- 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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe