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.
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