@inproceedings{28bb4ead14bf43cf9c54c359ce2355e5,
title = "Dover: An optimal on-line scheduling algorithm for overloaded real-time systems",
abstract = "Every task in a real-time system has a deadline by which time it should complete and a vaJue that it obtains only if it completes by its deadline. The problem is to design an on-line scheduling algorithm (i.e., the scheduler has no knowledge of a task until it is released) that maximizes the obtained value. When such a system is underloaded (i.e. there exists a schedule for which all tasks meet their deadlines), Dertouzos showed that the earliest deadline first algorithm will achieve 100% of the possible value. Locke showed that earliest deadline first performs very badly when the system is overloaded and proposed heuristics to deal with overload. Baruah et al. showed that the best that an on-line algorithm can guarantee is 1/(1+k)2 of the value that an off-line (clairvoyant) algorithm can obtain where k is the ratio between the highest value density and the lowest value density task in the system (where the value density of a task is its value divided by its computation time). We present an on-line algorithm that achieves the above best possible guarantee in this model. This algorithm also obtains 100% of the possible value when the system is underloaded.",
author = "Gilad Koren and Dennis Shasha",
year = "1992",
doi = "10.1109/REAL.1992.242650",
language = "English (US)",
isbn = "0818631953",
series = "Proceedings - Real-Time Systems Symposium",
pages = "290--299",
booktitle = "Proceedings - Real-Time Systems Symposium, RTSS 1992",
note = "1992 Real-Time Systems Symposium, RTSS 1992 ; Conference date: 02-12-1992 Through 04-12-1992",
}