000148550 001__ 148550
000148550 005__ 20190812205412.0
000148550 02470 $$2ISI$$a000286345400026
000148550 037__ $$aCONF
000148550 245__ $$aScheduling periodic tasks in a hard real-time environment
000148550 269__ $$a2010
000148550 260__ $$bSpringer-Verlag$$c2010
000148550 336__ $$aConference Papers
000148550 490__ $$aLecture Notes in Computer Science
000148550 520__ $$aWe 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.
000148550 6531_ $$aperiodic scheduling
000148550 6531_ $$areal-time scheduling
000148550 6531_ $$aapproximation algorithms
000148550 6531_ $$aperiodic maintenance problem
000148550 6531_ $$ahardness of approximation
000148550 700__ $$0240331$$g183121$$aEisenbrand, Friedrich
000148550 700__ $$0243824$$g188828$$aHähnle, Nicolai
000148550 700__ $$0243825$$g190205$$aNiemeier, Martin
000148550 700__ $$aSkutella, Martin
000148550 700__ $$aVerschae, José
000148550 700__ $$aWiese, Andreas
000148550 7112_ $$dJuly 5-10, 2010$$cBordeaux, France$$a37th International Colloquium on Automata, Languages and Programming (ICALP2010)
000148550 773__ $$j37$$t37th International Colloquium on Automata, Languages and Programming (ICALP2010)$$q299-311
000148550 8564_ $$zn/a$$yn/a$$uhttps://infoscience.epfl.ch/record/148550/files/ICALP-periodic-maintenance.pdf$$s138390
000148550 909C0 $$xU11879$$pDISOPT$$0252111
000148550 909CO $$ooai:infoscience.tind.io:148550$$qGLOBAL_SET$$pconf$$pSB
000148550 917Z8 $$x190205
000148550 917Z8 $$x190205
000148550 937__ $$aEPFL-CONF-148550
000148550 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000148550 980__ $$aCONF