TY - GEN
T1 - Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete
AU - Ekberg, Pontus
AU - Yi, Wang
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/8/3
Y1 - 2015/8/3
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84953373761
U2 - 10.1109/ECRTS.2015.32
DO - 10.1109/ECRTS.2015.32
M3 - 会议稿件
AN - SCOPUS:84953373761
T3 - Proceedings - Euromicro Conference on Real-Time Systems
SP - 281
EP - 286
BT - Proceedings - 27th Euromicro Conference on Real-Time Systems, ECRTS 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 27th Euromicro Conference on Real-Time Systems, ECRTS 2015
Y2 - 7 July 2015 through 10 July 2015
ER -