direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 628-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

A PTAS for minimizing the total weighted completion time on identical parallel machines
Martin Skutella and Gerhard J. Woeginger
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.
primary: 90C27 Combinatorial optimization
secondary: 68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
approximation algorithm, approximation scheme, scheduling
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.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe