Scheduling periodic tasks

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

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of processors, assuming that the tasks have to be executed strictly periodically. We show that the problem is NP-complete in the strong sense, even in the case of a single processor, but that it is solvable in polynomial time if the periods and execution times are divisible. The latter condition generalizes the situation in which all periods and execution times are powers of 2. We also propose an approximation algorithm, which is based on successively assigning tasks to processors according to some priority rule.
Original languageEnglish
Pages (from-to)428-435
Number of pages8
JournalINFORMS Journal on Computing
Volume8
Issue number4
DOIs
Publication statusPublished - 1996
Externally publishedYes

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

  • Cite this