Scheduling periodic tasks

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

Research output: Contribution to journalArticleScientificpeer-review


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
Issue number4
Publication statusPublished - 1996
Externally publishedYes


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

Cite this