@inproceedings{274add03672545b081d1dc1b2d9f903f,
title = "On-line scheduling in the presence of overload",
abstract = "The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.",
author = "S. Baruah and G. Koren and B. Mishra and A. Raghunathan and L. Rosier and D. Shasha",
year = "1991",
month = dec,
language = "English (US)",
isbn = "0818624450",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
publisher = "Publ by IEEE",
pages = "100--110",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
note = "Proceedings of the 32nd Annual Symposium on Foundations of Computer Science ; Conference date: 01-10-1991 Through 04-10-1991",
}