Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling (full paper). Available at http://www.cs.unc.edu/~anderson/papers.html

The earliest-pseudo-deadline-first (EPDF) Pfair al-gorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal on more than two processors. In earlier work, Srinivasan and Ander-son established a sufficient per-task utilization restric-tion for ensuring a tardiness of at most one quantum under EPDF. They also conjectured that a tardiness bound of one quantum applies to systems that are not restricted in any way. In this paper, we present coun-terexamples that show that this conjecture is false. We also present sufficient utilization restrictions that are more liberal than theirs