EDF-schedulability of synchronous periodic task systems is coNP-hard

In the synchronous periodic task model, a set τ1,..., τn of tasks is given, each releasing jobs of running time ci with relative deadline di, at each integer multiple of the period pi. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. di ≤ pi, the EDF-schedule is feasible if and only if ∀Q ≥ 0: n∑ i=1 Q − di pi + 1 · ci ≤ Q. Though an enormous amount of literature deals with this topic, the complexity status of this test has remained unknown. We prove that testing EDF-schedulability of such a task system is (weakly) coNP-hard. This solves Problem 2 from the survey “Open Problems in Real-time Scheduling ” by Baruah & Pruhs. The hardness result is achieved by applying recent re-sults on inapproximability of Diophantine approxima-tion.