The complexity of multidimensional periodic scheduling

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1998-12, Vol.89 (1), p.213-242
Main Authors: Verhaegh, W.F.J., Lippens, P.E.R., Aarts, E.H.L., van Meerbergen, J.L., van der Werf, A.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorial optimization
Computational complexity
Computer science
control theory
systems
Exact sciences and technology
IC design
Mathematical programming
Operational research and scientific management
Operational research. Management science
Periodic scheduling
Scheduling, sequencing
Theoretical computing
Video signal processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(98)00112-7