Article ID: | iaor20023202 |
Country: | United States |
Volume: | 30 |
Issue: | 1 |
Start Page Number: | 83 |
End Page Number: | 100 |
Publication Date: | May 2001 |
Journal: | Algorithmica |
Authors: | Ravi S.S., Rosenkrantz D.J., Yu L. |
This paper addresses scheduling problems for tasks with release and execution times. We present a number of efficient and easy to implement algorithms for constructing schedules of minimum makespan when the number of distinct task execution times is fixed. For a set of independent tasks, our algorithm in the single processor case runs in time linear in the number of tasks; with precedence constraints, our algorithm runs in time linear in the sum of the number of tasks and the size of the precedence constraints. In the multiprocessor case, our algorithm constructs minimum makespan schedules for independent tasks with uniform execution times. The algorithm runs in O(m log n) time where n is the number of tasks and m is the number of processors.