A Heuristic of Scheduling Parallel Tasks and Its Analysis

Authors:
  • QWQingzhou Wang
    Qingzhou Wang
  • KCKam-Hoi Cheng
    Kam-Hoi Cheng

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.

This publication has 7 references indexed in Scilit: