Preemptive scheduling with release times and deadlines

✍ Scribed by Kwang Soo Hong; Joseph Y-T. Leung

• Publisher: Springer US
• Year: 1989
• Tongue: English
• Weight: 905 KB
• Volume: 1
• Category: Article
• ISSN: 0922-6443
• DOI: 10.1007/bf00365440

✦ Synopsis

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(n 3) 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.