Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard
Authors:
- Friedrich EisenbrandFEFriedrich Eisenbrand
- Thomas RothvoßTRThomas Rothvoß
- 1 November 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10528725,p. 397-406
Abstract
We show that response time computation for rate-monotonic,preemptive scheduling of periodic tasks is NP-hard under Turing reductions. More precisely, we show that the response time of a task cannot be approximated within any constant factor, unless P=NP.Keywords
This publication has 17 references indexed in Scilit:
- An improved lower bound for approximating Shortest Integer Relation in norm ()Information Processing Letters, 2007
- A Fully Polynomial-Time Approximation Scheme for Feasibility Analysis in Static-Priority Systems with Arbitrary Relative Deadlines2006
- The rate monotonic scheduling algorithm: exact characterization and average case behavior2003
- Non-approximability results for optimization problems on bounded degree instances2001
- Approximating good simultaneous Diophantine approximations is almost NP-hardLecture Notes in Computer Science, 1996
- Fixed priority pre-emptive scheduling: An historical perspectiveReal-Time Systems, 1995
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- NP-Complete decision problems for binary quadraticsJournal of Computer and System Sciences, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973