Scheduling periodic tasks with slack

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 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

Scheduling
Approximation algorithms
Computational complexity
NP-hard

Cite this

Korst, J.H.M. ; Aarts, E.H.L. ; Lenstra, J.K. / Scheduling periodic tasks with slack. In: INFORMS Journal on Computing. 1997 ; Vol. 9, No. 4. pp. 351-362.
@article{22b698718b7f4778879a6dd752e8659d,
title = "Scheduling periodic tasks with slack",
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.",
author = "J.H.M. Korst and E.H.L. Aarts and J.K. Lenstra",
year = "1997",
doi = "10.1287/ijoc.9.4.351",
language = "English",
volume = "9",
pages = "351--362",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

Scheduling periodic tasks with slack. / Korst, J.H.M.; Aarts, E.H.L.; Lenstra, J.K.

In: INFORMS Journal on Computing, Vol. 9, No. 4, 1997, p. 351-362.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Scheduling periodic tasks with slack

AU - Korst, J.H.M.

AU - Aarts, E.H.L.

AU - Lenstra, J.K.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

U2 - 10.1287/ijoc.9.4.351

DO - 10.1287/ijoc.9.4.351

M3 - Article

VL - 9

SP - 351

EP - 362

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -