A Heuristic of Scheduling Parallel Tasks and Its Analysis
Authors:
- Qingzhou WangQWQingzhou Wang
- Kam-Hoi ChengKCKam-Hoi Cheng
- 1 April 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (2) , 281-294
Abstract
This paper investigates the problem of nonreconfigurable, nonpreemptive scheduling of parallel tasks in a homogeneous system of processors. Given a task precedence graph where each task T may be executed on up to $\delta (T)$ processors, the problem is to find a schedule such that the makespan is minimized. A scheduling policy is nonreconfigurable if when more processors become available after a task T has been scheduled on p processors, $p < \delta (T)$, they cannot join the execution of task T. It is nonpreemptive if each task is executed without interruption until completion once the task has started execution. The problem of scheduling parallel tasks is NP-hard. The performance ratio of the makespan produced by the original list scheduling algorithm proposed by Graham [SIAM J. Appl. Math., 17 (1969), pp. 416–429] to the optimal makespan is $\Delta + \frac{m - \Delta} {m}$ [Inform. Process. Lett., 37 (1991), pp. 291–297], where m and $\Delta $ are the number of processors in the system and the maximum degree of parallelism in any task, respectively. To provide a performance improvement, the Earliest Completion Time (ECT) algorithm is proposed; it is also shown that its performance ratio is bounded by $3-\frac{2}{m}$. In addition, an example is presented to demonstrate that the bound is at least 2.5.
Keywords
This publication has 7 references indexed in Scilit:
- List scheduling of parallel tasksInformation Processing Letters, 1991
- Complexity of Scheduling Parallel Task SystemsSIAM Journal on Discrete Mathematics, 1989
- Scheduling Multiprocessor Tasks to Minimize Schedule LengthIEEE Transactions on Computers, 1986
- Bounds for List Schedules on Uniform ProcessorsSIAM Journal on Computing, 1980
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Bounds for LPT Schedules on Uniform ProcessorsSIAM Journal on Computing, 1977
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969