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 Con-gruences Problem to the complement of the feasibility problem. I