ISSN:
1573-1383
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00365440
