Approximation schemes for minimizing average weighted completion time with release dates

Author

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

Author_Institution

Div. of Comput. Sci., NTUA, Athens, Greece

fYear

1999

fDate

1999

Firstpage

32

Lastpage

43

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)

Keywords

computational complexity; scheduling; average weighted completion time; minimizing average weighted completion time; parallel machines; polynomial time approximation; scheduling; Approximation algorithms; Computer science; Contracts; Educational institutions; Engineering profession; Informatics; Laboratories; Mathematics; Parallel machines; Power generation economics;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 1999. 40th Annual Symposium on

Conference_Location

New York City, NY

ISSN

0272-5428

Print_ISBN

0-7695-0409-4

Type

conf

DOI

10.1109/SFFCS.1999.814574

Filename

814574