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

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