DocumentCode
729440
Title
Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete
Author
Ekberg, Pontus ; Wang Yi
Author_Institution
Uppsala Univ., Uppsala, Sweden
fYear
2015
fDate
8-10 July 2015
Firstpage
281
Lastpage
286
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.
Keywords
computational complexity; scheduling; NP-hard simultaneous congruences problem; coNP-Complete; computational complexity; constrained deadlines; preemptive uniprocessor; pseudo-polynomial transformation; real-time scheduling theory; sporadic task system; uniprocessor feasibility; Computational complexity; Electronic mail; Polynomials; Processor scheduling; Real-time systems; Resumes;
fLanguage
English
Publisher
ieee
Conference_Titel
Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on
Conference_Location
Lund
Type
conf
DOI
10.1109/ECRTS.2015.32
Filename
7176045
Link To Document