Technical Report 640-1999

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

Source

Download as [PDF] [ps.gz]

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.

See also

Publications of Martin Skutella