Scheduling periodic tasks

Scheduling periodic tasks

0.00 Avg rating0 Votes
Article ID: iaor19982703
Country: United States
Volume: 8
Issue: 4
Start Page Number: 428
End Page Number: 435
Publication Date: Sep 1996
Journal: INFORMS Journal On Computing
Authors: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.