License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10071.13
URN: urn:nbn:de:0030-drops-25348
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2534/
Go to the corresponding Portal

Eisenbrand, Friedrich ; Hähnle, Nicolai ; Niemeier, Martin ; Skutella, Martin ; Verschae, Jose ; Wiese, Andreas

Scheduling periodic tasks in a hard real-time environment

pdf-format:
10071.NiemeierMartin.ExtAbstract.2534.pdf (0.08 MB)

Abstract

We consider a real-time scheduling problem that occurs in the design
of software-based 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^{1-varepsilon}$ 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 2-approximation. This result is tight, even asymptotically.

BibTeX - Entry

@InProceedings{eisenbrand_et_al:DagSemProc.10071.13,
  author =	{Eisenbrand, Friedrich and H\"{a}hnle, Nicolai and Niemeier, Martin and Skutella, Martin and Verschae, Jose and Wiese, Andreas},
  title =	{{Scheduling periodic tasks in a hard real-time environment}},
  booktitle =	{Scheduling},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2534},
  URN =		{urn:nbn:de:0030-drops-25348},
  doi =		{10.4230/DagSemProc.10071.13},
  annote =	{Keywords: Real-Time Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm}
}

Keywords: Real-Time Scheduling, Periodic scheduling problem, Periodic maintenance problem, Approximation hardness, Approximation algorithm
Collection: 10071 - Scheduling
Issue Date: 2010
Date of publication: 03.05.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI