Performance guarantee for EDF under overload

Earliest deadline first (EDF) is a widely used algorithm for online deadline scheduling. It has been known for long that EDF is optimal for scheduling an underloaded, single-processor system; recent results on the extra-resource analysis of EDF further revealed that EDF when using moderately faster processors can achieve optimal performance in the underloaded, multi-processor setting. This paper initiates the extra-resource analysis of EDF for overloaded systems, showing that EDF supplemented with a simple form of admission control can provide a similar performance guarantee in both the single and multi-processor settings. © 2003 Elsevier Inc. All rights reserved.postprin