Scheduling periodic tasks in a hard real-time environment

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



PDF
Thumbnail PDF

File

DagSemProc.10071.13.pdf
  • Filesize: 83 kB
  • 3 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, Jose Verschae, and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.10071.13

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.
Keywords
  • Real-Time Scheduling
  • Periodic scheduling problem
  • Periodic maintenance problem
  • Approximation hardness
  • Approximation algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail