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.10
URN: urn:nbn:de:0030-drops-25458
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2545/
Go to the corresponding Portal

Eisenbrand, Friedrich ; Rothvoss, Thomas

Recent Hardness Results for Periodic Uni-processor Scheduling

pdf-format:
10071.RothvossThomas.ExtAbstract.2545.pdf (0.2 MB)

Abstract

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.


BibTeX - Entry

@InProceedings{eisenbrand_et_al:DagSemProc.10071.10,
  author =	{Eisenbrand, Friedrich and Rothvoss, Thomas},
  title =	{{Recent Hardness Results for Periodic Uni-processor Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--7},
  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/2545},
  URN =		{urn:nbn:de:0030-drops-25458},
  doi =		{10.4230/DagSemProc.10071.10},
  annote =	{Keywords: Hardness, periodic scheduling, uni-processor scheduling}
}

Keywords: Hardness, periodic scheduling, uni-processor scheduling
Collection: 10071 - Scheduling
Issue Date: 2010
Date of publication: 03.05.2010

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