Eisenbrand, Friedrich ;
Rothvoss, Thomas
Recent Hardness Results for Periodic Uni-processor Scheduling
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:DSP:2010:2545,
author = {Friedrich Eisenbrand and Thomas Rothvoss},
title = {Recent Hardness Results for Periodic Uni-processor Scheduling},
booktitle = {Scheduling},
year = {2010},
editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M{\"o}hring and Kirk Pruhs},
number = {10071},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2545},
annote = {Keywords: Hardness, periodic scheduling, uni-processor scheduling}
}
|
Keywords: |
|
Hardness, periodic scheduling, uni-processor scheduling |
|
Seminar: |
|
10071 - Scheduling
|
|
Issue date: |
|
2010 |
|
Date of publication: |
|
03.05.2010 |
03.05.2010
