Scheduling periodic tasks with slack

J.H.M. Korst, E.H.L. Aarts, J.K. Lenstra

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)


We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of identical processors, assuming that some slack is allowed in the time between successive executions of a periodic task. We prove that the problem is NP-hard in the strong sense. Necessary and sufficient conditions are derived for scheduling two periodic tasks on a single processor, and for combining two periodic tasks into one larger task. Based on these results, we propose an approximation algorithm.
Original languageEnglish
Pages (from-to)351-362
JournalINFORMS Journal on Computing
Issue number4
Publication statusPublished - 1997


Dive into the research topics of 'Scheduling periodic tasks with slack'. Together they form a unique fingerprint.

Cite this