Inhalt des Dokuments
Preprint 640-1999
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
- Authors
- Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein, and Maxim Sviridenko
- Publication
- in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 32-43
- 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 jobs with release dates on parallel machines so as to minimize average weighted completion time. While constant factor approximation algorithms for many variants have been developed in the last few years, we present the first known polynomial time approximation schemes for several of them. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our PTASs are also efficient. For most variants, the running time for a (1+ε)-approximation on an instance with n jobs and m machines is O(nlog n) for each fixed ε, and for all variants the running time's dependence on n is a fixed polynomial whose degree is independent of ε and m.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe