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, ?, may be chosen for the approximation scheme, and present a runtime bound that is polynomial in terms of ? and the number of tasks, n.