Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times |
| |
Authors: | D J Rosenkrantz L Yu S S Ravi |
| |
Affiliation: | (1) Department of Computer Science, University at Albany, State University of New York, Albany, NY 12222, USA. \{djr, linyu, ravi\}@cs.albany.edu. Supported by NSF Grant CCR-97-34936., US |
| |
Abstract: | 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 multi-processor case, our algorithm constructs minimum makespan schedules for independent tasks
with uniform execution times. The algorithm runs in O(n log m) time where n is the number of tasks and m is the number of processors.
Received September 25, 1997; revised June 11, 1998. |
| |
Keywords: | , Task scheduling, Release time, Execution time, Makespan, Single and multiple processors, Algorithm design and analysis, |
本文献已被 SpringerLink 等数据库收录! |
|