The Partitioned EDF Scheduling of Sporadic Task Systems

The partitioned scheduling of sporadic task systems on identical multiprocessors is considered. This is known to be intractable (NP-hard in the strong sense). A polynomial-time approximation scheme (PTAS) is proposed for sporadic task systems satisfying the additional constraint that for each of the three parameters -- worst-case execution time, relative deadline, and period -- that characterize sporadic tasks, the ratio of the largest value to the smallest value is bounded from above by a constant.