Faster approximation algorithms for scheduling with fixed jobs
2011 (English)In: Conferences in Research and Practice in Information Technology Series, 2011, 3-9 p.Conference paper (Refereed)
We study the problem of scheduling jobs on identical parallel machines without preemption. In the considered setting, some of the jobs are already assigned machines and starting times, for example due to external constraints not explicitly modelled. The objective is to assign the rest of the jobs in order to minimize the makespan. It is known that this problem cannot be approximated better than within a factor of 3/2 unless P = NP. An algorithm that achieves 3/2 + ε for any ε > 0 was presented by Diedrich and Jansen [DJ09], but its running time is doubly exponential in 1/ε. We present an improved algorithm with approximation ratio 3/2 and polynomial running time. We also give matching results for the related problem of scheduling with reservations. The new algorithm is both faster and conceptually simpler than the previously known algorithms.
Place, publisher, year, edition, pages
2011. 3-9 p.
, Conferences in Research and Practice in Information Technology Series, ISSN 1445-1336 ; 119
Approximation ratios, External constraints, Fixed jobs, Identical parallel machines, Makespan, Running time, Scheduling jobs, Approximation algorithms, Business machines, Polynomial approximation, Scheduling, Scheduling algorithms, Computation theory
IdentifiersURN: urn:nbn:se:kth:diva-149759ScopusID: 2-s2.0-84864606866ISBN: 9781920682989OAI: oai:DiVA.org:kth-149759DiVA: diva2:749289
Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011, 17 January 2011 through 20 January 2011, Perth, WA
QC 201409232014-09-232014-08-272014-09-23Bibliographically approved