Number of Processors with Partitioning Strategy and EDF-Schedulability Test: Upper and Lower Bounds with Comparison.

In this paper, 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 scenario 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 paper. Numerical results demonstrate that our lower bound is very tight and it is very close to the optimal solution. [ABSTRACT FROM AUTHOR]