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

Abstract

We show that response time computation for Rate-monotonic,preemptive scheduling of periodic tasks is NP-hard under Turingreductions. More precisely, we show that the response time of a taskcannot be approximated within any constant factor, unless P=NP.