Approximation schemes for minimizing average weighted completion time with release dates
- Resource Type
- Conference
- Authors
- Afrati, F.; Bampis, E.; Chekuri, C.; Karger, D.; Kenyon, C.; Khanna, S.; Milis, I.; Queyranne, M.; Skutella, M.; Stein, C.; Sviridenko, M.
- Source
- 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) Foundations of computer science Foundations of Computer Science, 1999. 40th Annual Symposium on. :32-43 1999
- Subject
- Computing and Processing
Approximation algorithms
Parallel machines
Computer science
Contracts
Mathematics
Laboratories
Power generation economics
Informatics
Educational institutions
Engineering profession
- Language
- ISSN
- 0272-5428
We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).