Thumbnail Image

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

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

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

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.