@conference{response-time-NP-hard,
author = "Friedrich Eisenbrand and Thomas Rothvo{\ss}",
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 = 0: \sum_{i=1}^n (floor(Q-d_i)/p_i) + 1) * c_i ls 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.",
booktitle = "21st {S}ymposium on {D}iscrete {A}lgorithms ({SODA} 2010)",
keywords = "periodic scheduling; complexity theory",
pages = "1029--1034",
title = "{EDF}-schedulability of synchronous periodic task systems is co{NP}-hard",
url = "http://www.siam.org/proceedings/soda/2010/SODA10_083_eisenbrandf.pdf",
year = "2010",
}