Approximating real-time scheduling on identical machines

N. Bansal, C. Rutten, S. Ster, van der, T. Vredeveld, G.R.J. Zwaan, van der

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)


We study the problem of assigning n tasks to m identical parallel machines in the real-time scheduling setting, where each task recurrently releases jobs that must be completed by their deadlines. The goal is to find a partition of the task set over the machines such that each job that is released by a task can meet its deadline. Since this problem is co-NP-hard, the focus is on finding a-approximation algorithms in the resource augmentation setting, i.e., finding a feasible partition on machines running at speed a¿=¿1, if some feasible partition exists on unit-speed machines. Recently, Chen and Chakraborty gave a polynomial-time approximation scheme if the ratio of the largest to the smallest relative deadline of the tasks, ¿, is bounded by a constant. However, their algorithm has a super-exponential dependence on ¿ and hence does not extend to larger values of ¿. Our main contribution is to design an approximation scheme with a substantially improved running-time dependence on ¿. In particular, our algorithm depends exponentially on log¿ and hence has quasi-polynomial running time even if ¿ is polynomially bounded. This improvement is based on exploiting various structural properties of approximate demand bound functions in different ways, which might be of independent interest.
Original languageEnglish
Title of host publicationLATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)
EditorsA. Pardo, A. Viola
Place of PublicationBerlin
ISBN (Print)978-3-642-54422-4
Publication statusPublished - 2014
Event11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 2014
Conference number: 11

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference11th Latin American Theoretical INformatics Symposium (LATIN 2014)
Abbreviated titleLATIN 2014


Dive into the research topics of 'Approximating real-time scheduling on identical machines'. Together they form a unique fingerprint.

Cite this