TY - JOUR
T1 - Approximation schemes for minimizing average weighted completion time with release dates
AU - Afrati, Foto
AU - Bampis, Evripidis
AU - Chekuri, Chandra
AU - Karger, David
AU - Kenyon, Claire
AU - Khanna, Sanjeev
AU - Milis, Ioannis
AU - Queyranne, Maurice
AU - Skutella, Martin
AU - Stein, Cliff
AU - Sviridenko, Maxim
PY - 1999
Y1 - 1999
N2 - 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 a (1 + qq) approximation is of the form f(1/qq, m)poly(n).
AB - 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 a (1 + qq) approximation is of the form f(1/qq, m)poly(n).
UR - http://www.scopus.com/inward/record.url?scp=0032606578&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032606578&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:0032606578
SN - 0272-5428
SP - 32
EP - 43
JO - Annual Symposium on Foundations of Computer Science - Proceedings
JF - Annual Symposium on Foundations of Computer Science - Proceedings
T2 - Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science
Y2 - 17 October 1999 through 19 October 1999
ER -