Change search
ReferencesLink to record
Permanent link

Direct link
Faster approximation algorithms for scheduling with fixed jobs
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2011 (English)In: Conferences in Research and Practice in Information Technology Series, 2011, 3-9 p.Conference paper (Refereed)
Abstract [en]

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
Keyword [en]
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
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-149759ScopusID: 2-s2.0-84864606866ISBN: 9781920682989OAI: diva2:749289
Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011, 17 January 2011 through 20 January 2011, Perth, WA

QC 20140923

Available from: 2014-09-23 Created: 2014-08-27 Last updated: 2014-09-23Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Svensson, Ola
By organisation
Theoretical Computer Science, TCS
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link