Approximation schemes for minimizing average weighted completion time with release dates

Foto Afrati, Evripidis Bampis, Chandra Chekuri, David Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Cliff Stein, Maxim Sviridenko

Research output: Contribution to journalConference articlepeer-review

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 a (1 + qq) approximation is of the form f(1/qq, m)poly(n).

Original languageEnglish (US)
Pages (from-to)32-43
Number of pages12
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Approximation schemes for minimizing average weighted completion time with release dates'. Together they form a unique fingerprint.

Cite this