@inproceedings{2dccdaad347e42b4a4698af634866048,
title = "On the competitiveness of on-line real-time task scheduling",
abstract = "The authors study the performance of online algorithms in environments where no value is obtained for the partial execution of a request. They prove that no online scheduling algorithm can have a competitive factor greater than 0.25 times the optimal. They further refine this bound by considering the effect of the loading factor. Other models of task systems (for example, task systems consisting of many types of task requests), are considered. Similar upper bounds on the competitive factor that can be made by online scheduling algorithms in these environments are proved. It is shown that the performance bound of 0.25 is tight by means of a simple online uniprocessor scheduling algorithm has a competitive factor of 1/4. The authors extend the discussion to systems with dual processors. They show that the upper bound for the dual-processor online scheduling problem is 1/2 if all tasks have the same value density. This bound is tight if the tasks all also have zero laxity.",
author = "S. Baruah and G. Koren and D. Mao and B. Mishra and A. Raghunathan and L. Rosier and D. Shasha and F. Wang",
year = "1991",
language = "English (US)",
isbn = "0818624507",
series = "Proceedings - Real-Time Systems Symposium",
publisher = "Publ by IEEE",
pages = "107--115",
booktitle = "Proceedings - Real-Time Systems Symposium",
note = "Proceedings of the 12th Real-Time Systems Symposium ; Conference date: 04-12-1991 Through 06-12-1991",
}