A fully polynomial-time approximation scheme for feasibility analysis in static-priority systems with arbitrary relative deadlines

Current feasibility tests for the static-priority scheduling on uniprocessors of periodic task systems run in pseudo-polynomial time. We present a fully polynomial-time approximation scheme (FPTAS) for feasibility analysis in static-priority systems with arbitrary relative deadlines. This test is an approximation with respect to the amount of a processor's capacity that must be "sacrificed" for the test to become exact. We show that an arbitrary level of accuracy, E, may be chosen for the approximation scheme, and present a runtime bound that is polynomial in terms of c and the number of tasks, n.