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 processorusing inserted idle times. For periodic task systems, we prove that the decision problem of determiningwhether a periodic task system is schedulable for all start times with respect to the class of algorithms usinginserted idle times is NP-Hard in the strong sense, even when the deadlines are equal to the periods. We thenshow that if there exists a polynomial time scheduling algorithm...