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 arbi-trary 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, , may be cho-sen for the approximation scheme, and present a run-time bound that is polynomial in terms of and the num-ber of tasks, n