Scheduling cyclic tasks with binary periods

We show that static scheduling of cyclic non-preemptable tasks with binary periods which are to be executed on one processor is strongly NP-hard. To solve the problem a simple but efficient heuristic strategy is proposed.

Saved in:
Bibliographic Details
Published in:Information processing letters 1998-02, Vol.65 (4), p.173-178
Main Authors: Nawrocki, Jerzy R., Czajka, Adam, Complak, Wojciech
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorial problems
Computational complexity
Computer science
control theory
systems
Cyclic tasks
Exact sciences and technology
Heuristic
Information processing
Real time
Real-time systems
Scheduling
Studies
Theoretical computing
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 show that static scheduling of cyclic non-preemptable tasks with binary periods which are to be executed on one processor is strongly NP-hard. To solve the problem a simple but efficient heuristic strategy is proposed.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(98)00221-X