@inproceedings{EisenbrandRothvoss2010,
Title = {EDF-schedulability of synchronous periodic task systems is coNP-hard},
Author = {Eisenbrand, Friedrich and Rothvo\ss, Thomas},
Booktitle = {Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)},
Pages = {1029--1034},
Year = {2010},
Abstract = {In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) is an optimal preemptive uni-processor scheduling policy. For constrained deadlines, i.e. d_i <= p_i, the EDF-schedule is feasible if and only if for all Q >= 0: \sum_i=1^n (floor(Q-d_i)/p_i) + 1) * c_i <= 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 results on inapproximability of Diophantine approximation.},
Url = {http://infoscience.epfl.ch/getfile.py?recid=141575&mode=best},
Keywords = {periodic scheduling; complexity theory},
Projectname = {SPP-RTS-Routing}
}