Preemptive scheduling with release times and deadlines

Kwang Soo Hong, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We consider the problem of deciding if there is a feasible preemptive schedule for a set of n independent tasks with release times and deadlines on m identical processors. The general problem is known to be solvable in O(n3) time. In this paper, we study special cases for which faster algorithms exist. We introduce the notion of monotone schedules and study their properties. These properties are then exploited to devise fast algorithms for two special cases-the nested task systems and the non-overlapping task systems. We give an O(n log mn) time algorithm and an O(n log n+mn) time algorithm for nested task systems and non-overlapping task systems, respectively. Our algorithms generate at most O(n) and O(mn) preemptions for nested task systems and nonoverlapping task systems, respectively.

Original languageEnglish (US)
Pages (from-to)265-281
Number of pages17
JournalReal-Time Systems
Issue number3
StatePublished - Dec 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Modeling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering


Dive into the research topics of 'Preemptive scheduling with release times and deadlines'. Together they form a unique fingerprint.

Cite this