On the competitiveness of on-line real-time task scheduling

S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, F. Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings - Real-Time Systems Symposium
PublisherPubl by IEEE
Number of pages9
ISBN (Print)0818624507
StatePublished - 1991
EventProceedings of the 12th Real-Time Systems Symposium - San Antonio, TX, USA
Duration: Dec 4 1991Dec 6 1991

Publication series

NameProceedings - Real-Time Systems Symposium


OtherProceedings of the 12th Real-Time Systems Symposium
CitySan Antonio, TX, USA

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'On the competitiveness of on-line real-time task scheduling'. Together they form a unique fingerprint.

Cite this