Scheduling periodic tasks with slack

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

Research output: Contribution to journalArticleScientificpeer-review

8 Citations (Scopus)

Abstract

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
Number of pages12
JournalINFORMS Journal on Computing
Volume9
Issue number4
DOIs
Publication statusPublished - 1997
Externally publishedYes

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

  • Cite this