Static-Priority Real-Time Scheduling: Response Time Computation Is NP-Hard

Authors:
  • FEFriedrich Eisenbrand
    Friedrich Eisenbrand
  • TRThomas Rothvoß
    Thomas Rothvoß

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.

This publication has 17 references indexed in Scilit: