On Non-Preemptive Scheduling of Recurring Tasks Using Inserted Idle Times

We consider the problem of non-preemptively scheduling periodic and sporadic task systems on one processor using inserted idle times. For periodic task systems, we prove that the decision problem of determining whether a periodic task system is schedulable for all start times with respect to the class of algorithms using inserted idle times is NP-Hard in the strong sense, even when the deadlines are equal to the periods. We then show that if there exists a polynomial time scheduling algorithm which correctly schedules a periodic task system T whenever T is feasible for all start times, then P=NP. We also prove that with respect to the same class of algorithms, the problem of determining whether there exist start times for which a periodic task system is feasible is also NP-Hard in the strong sense even when the deadlines are equal to the periods. The second part of the paper concentrates on sporadic task systems and inserted idle times. It seems reasonable to suppose that to insert idl..