Technical Report Number 2007-535 Number of Processors for Scheduling a Set of Real-Time Tasks: Upper and Lower Bounds ∗
Arezou Mohammadi, Selim G. Akl · 2007
In this report, we study the problem of scheduling a set of n periodic preemptive independent hard real-time tasks on the minimum number of processors. We assume that the partitioning strategy is used to allocate the tasks to the processors and the EDF method is used to schedule the tasks on each processor. It is known that this problem is NP-hard; thus, it is unlikely to find a polynomial time algorithm to schedule the tasks on the minimum number of processors. In this work, we derive a lower and an upper bound for the number of processors required to satisfy the constraints of our problem. We also compare a number of heuristic algorithms with each other and with the bounds derived in this report. Numerical results demonstrate that our lower bound is very tight and it is very close to the optimal solution.