2026-07-21T14:19:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2534 2024-03-06T11:09:10Z ddc:004 open_access

Scheduling periodic tasks in a hard real-time environment Eisenbrand, Friedrich Hähnle, Nicolai Niemeier, Martin Skutella, Martin Verschae, Jose Wiese, Andreas Real-Time Scheduling Periodic scheduling problem Periodic maintenance problem Approximation hardness Approximation algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Friedrich Eisenbrand and Nicolai Hähnle and Martin Niemeier and Martin Skutella and Jose Verschae and Andreas Wiese 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10071.13 urn:nbn:de:0030-drops-25348 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.13 eng https://creativecommons.org/licenses/by/4.0/legalcode