Improved conditions for bounded tardiness under EPDF fair multiprocessor scheduling

The earliest-pseudo-deadline-first (EPDF) Pfair algorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal on more than two processors. In earlier work, Srinivasan and Anderson established a sufficient per-task utilization restriction 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 counterexamples that show that this conjecture is false. We also present sufficient utilization restrictions that are more liberal than theirs