Parametric Polynomial-Time Algorithms for Computing ResponseTime Bounds for Static-Priority Tasks with Release Jitters

Feasibility analysis algorithms are based on particular metrics such as processor utilization, load factor, proces-sor demand, response-times, etc. The design of efficient al-gorithms for computing these metrics is a major issue in real-time scheduling theory. In this paper we propose two FPTASs (fully-polynomial time approximation schemes) for checking feasibility of static-priority tasks subjected to re-lease jitters executed upon a uniprocessor platform. We then use these FPTASs for computing two upper bounds of worst-case response-times. Lastly, we show that these bounds do not achieve constant error bounds in compari-son with values computed by an exact worst-case response-time analysis (performed in pseudo-polynomial time), and we present numerical experiments. 1