148550
20190812205412.0
ISI
000286345400026
CONF
Scheduling periodic tasks in a hard real-time environment
Springer-Verlag
2010
2010
Conference Papers
Lecture Notes in Computer Science
We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks $\tau_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 $\tau_i$ releases a job of running time $c_i$ at each time $a_i + k\cdot p_i$, $k\in\setN$ and a collision occurs if two jobs are simultaneously active on the same machine. Our main results are as follows: (i) We show that the minimization problem cannot be approximated within a factor of $n^{1-\epsilon}$ for any $\epsilon>0$. (ii) If the periods are dividing (for each $i,j$ one has $p_i \mid p_j$ or $p_j \mid p_i$), then there exists a 2-approximation for the minimization problem and this result is tight, even asymptotically. (iii) We provide asymptotic approximation schemes in the dividing case if the number of different periods is constant.
periodic scheduling
real-time scheduling
approximation algorithms
periodic maintenance problem
hardness of approximation
240331
Eisenbrand, Friedrich
183121
243824
Hähnle, Nicolai
188828
243825
Niemeier, Martin
190205
Skutella, Martin
Verschae, José
Wiese, Andreas
37th International Colloquium on Automata, Languages and Programming (ICALP2010)
Bordeaux, France
July 5-10, 2010
37
299-311
37th International Colloquium on Automata, Languages and Programming (ICALP2010)
138390
http://infoscience.epfl.ch/record/148550/files/ICALP-periodic-maintenance.pdf
n/a
n/a
252111
DISOPT
U11879
oai:infoscience.tind.io:148550
SB
conf
GLOBAL_SET
190205
190205
EPFL-CONF-148550
EPFL
REVIEWED
PUBLISHED
CONF