The complexity of multidimensional periodic scheduling

W.F.J. Verhaegh, P.E.R. Lippens, E.H.L. Aarts, J. Meerbergen van, A. Werf van der

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

Abstract

We discuss the computational complexity of the multidimensional periodic scheduling problem. This problem originates from the assignment of periodic tasks to processing units over time and it is related to the design of high-performance video signal processors. We present a model of multidimensional periodic operations and introduce the multidimensional periodic scheduling problem. Next, we show that this problem and two related sub-problems are NP-hard. Further-more, we identify several special cases induced by practical situations, of which some are proven to be polynomially solvable.
Original languageEnglish
Pages (from-to)213-242
Number of pages30
JournalDiscrete Applied Mathematics
Volume89
Issue number1-3
DOIs
Publication statusPublished - 1998
Externally publishedYes

Fingerprint Dive into the research topics of 'The complexity of multidimensional periodic scheduling'. Together they form a unique fingerprint.

  • Cite this

    Verhaegh, W. F. J., Lippens, P. E. R., Aarts, E. H. L., Meerbergen van, J., & Werf van der, A. (1998). The complexity of multidimensional periodic scheduling. Discrete Applied Mathematics, 89(1-3), 213-242. https://doi.org/10.1016/S0166-218X(98)00112-7