Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete

Abstract

Deciding the feasibility of a sporadic task system on a preemptive uniprocessor is a central problem in real-time scheduling theory. The computational complexity of this problem has been a long-standing open question. We show that it is coNP-complete in the strong sense, even when deadlines are constrained. This is achieved by means of a pseudo-polynomial transformation from the strongly NP-hard Simultaneous Congruences Problem to the complement of the feasibility problem.