Approximating real-time scheduling on identical machines

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (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.
Originele taal-2Engels
TitelLATIN 2014: Theoretical Informatics (11th Latin American Symposium, Montevideo, Uruguay, March 31-April 4, 2014. Proceedings)
RedacteurenA. Pardo, A. Viola
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-54422-4
StatusGepubliceerd - 2014
Evenement11th Latin American Theoretical INformatics Symposium (LATIN 2014) - Montevideo, Uruguay
Duur: 31 mrt. 20144 apr. 2014
Congresnummer: 11

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Congres11th Latin American Theoretical INformatics Symposium (LATIN 2014)
Verkorte titelLATIN 2014
Ander11th Latin American Symposium on Theoretical Informatics


Duik in de onderzoeksthema's van 'Approximating real-time scheduling on identical machines'. Samen vormen ze een unieke vingerafdruk.

Citeer dit