Approximation schemes for minimizing average weighted completion time with release dates. Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., & Sviridenko, M. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 32--43, 1999.
doi  abstract   bibtex   
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 α(1+ε) approximation is of the form f(1/ε, m)poly(n)
@inproceedings{afrati_approximation_1999,
	title = {Approximation schemes for minimizing average weighted completion time with release dates},
	doi = {10.1109/SFFCS.1999.814574},
	abstract = {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 α(1+ε) approximation
is of the form f(1/ε, m)poly(n)},
	booktitle = {Foundations of {Computer} {Science}, 1999. 40th {Annual} {Symposium} on},
	author = {Afrati, F. and Bampis, E. and Chekuri, C. and Karger, D. and Kenyon, C. and Khanna, S. and Milis, I. and Queyranne, M. and Skutella, M. and Stein, C. and Sviridenko, M.},
	year = {1999},
	keywords = {average weighted completion time, computational complexity, minimizing average weighted completion time, parallel machines, polynomial time approximation},
	pages = {32--43}
}

Downloads: 0