2026-07-24T17:55:50Z https://drops.dagstuhl.de/oai

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

Recent Hardness Results for Periodic Uni-processor Scheduling Eisenbrand, Friedrich Rothvoss, Thomas Hardness periodic scheduling uni-processor scheduling Consider a set of $n$ periodic tasks $ au_1,ldots, au_n$ where $ au_i$ is described by an execution time $c_i$, a (relative) deadline $d_i$ and a period $p_i$. We assume that jobs are released synchronously (i.e. at each multiple of $p_i$) and consider pre-emptive, uni-processor schedules. We show that computing the response time of a task $ au_n$ in a Rate-monotonic schedule i.e. computing [ minleft{ r geq mid c_n + sum_{i=1}^{n-1} leftlceil frac{r}{p_i} ight ceil c_i leq r ight} ] is (weakly) $mathbf{NP}$-hard (where $ au_n$ has the lowest priority and the deadlines are implicit, i.e. $d_i = p_i$). Furthermore we obtain that verifying EDF-schedulability, i.e. [ forall Q geq 0: sum_{i=1}^n left( leftlfloor frac{Q-d_i}{p_i} ight floor +1 ight)cdot c_i leq Q ] for constrained-deadline tasks ($d_i leq p_i$) is weakly $mathbf{coNP}$-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Friedrich Eisenbrand and Thomas Rothvoss 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10071.10 urn:nbn:de:0030-drops-25458 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.10 eng https://creativecommons.org/licenses/by/4.0/legalcode