Eisenbrand, Friedrich ;
Hähnle, Nicolai ;
Niemeier, Martin ;
Skutella, Martin ;
Verschae, Jose ;
Wiese, Andreas
Scheduling periodic tasks in a hard realtime environment
Abstract
We consider a realtime scheduling problem that occurs in the design
of softwarebased aircraft control. The goal is to distribute tasks
$ au_i=(c_i,p_i)$ on a minimum number of identical machines and to
compute offsets $a_i$ for the tasks such that no collision occurs. A
task $ au_i$ releases a job of running time $c_i$ at each time $a_i +
kcdot p_i, , k in mathbb{N}_0$ and a collision occurs if two jobs are
simultaneously active on the same machine.
We shed some light on the complexity and approximability landscape of this problem.
Although the problem cannot be approximated
within a factor of $n^{1varepsilon}$ for any $varepsilon>0$, an interesting restriction
is much more tractable: If the periods are dividing (for each $i,j$ one has $p_i 
p_j$ or $p_j  p_i$), the problem allows for a better structured representation of solutions, which leads
to a 2approximation. This result is tight, even asymptotically.
BibTeX  Entry
@InProceedings{eisenbrand_et_al:DSP:2010:2534,
author = {Friedrich Eisenbrand and Nicolai H{\"a}hnle and Martin Niemeier and Martin Skutella and Jose Verschae and Andreas Wiese},
title = {Scheduling periodic tasks in a hard realtime environment},
booktitle = {Scheduling},
year = {2010},
editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M{\"o}hring and Kirk Pruhs},
number = {10071},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2534},
annote = {Keywords: RealTime Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm}
}
03.05.2010
Keywords: 

RealTime Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm 
Seminar: 

10071  Scheduling

Issue date: 

2010 
Date of publication: 

03.05.2010 