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.