Dover; an optimal on-line scheduling algorithm for overloaded real-time systems

An optimal online scheduling algorithm for overloaded systems is presented. It is optimal in the sense that it gives the best competitive factor possible relative to an offline (i.e., clairvoyant) scheduler. It also gives 100% of the value of a clairvoyant scheduler when the system is underloaded. In fact the performance guarantee of D^over is even stronger: D^over schedules to completion all tasks in underloaded periods and achieves at least 1/(1+√k)² of the value a clairvoyant algorithm can get during overloaded periods. The model accounts for different value densities and generalizes to soft deadlines