Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates
Author(s): Afrati, Foto
Bampis, Evripidis
Chekuri, Chandra
Karger, David
Kenyon, Claire
Khanna, Sanjeev
Milis, Ioannis
Queyranne, Maurice
Skutella, Martin
Stein, Cliff
Sviridenko, Maxim
Type: Research Paper
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.
Subject(s): approximation algorithm
approximation scheme
completion time
release dates
Issue Date: 1999
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1999, 640
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 185.91 kB
DownloadShow Preview
Format: Unknown | Size: 77.7 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.