Algorithms for handling skew in parallel task scheduling

Abstract

In this paper we consider the problem of scheduling a collection of independent tasks on multiple processors (denote the number of processors by p) so that the maximum completion time is minimized. We present two new algorithms, the LPT-MinHeight (LPTMH) algorithm and the Split-LPT(SLPT) algorithm. Both algorithms are based on the LPT(Largest Processing Time first) algorithm. The worst case imbalance for the LPTMH algorithm never exceeds 1/(e - 1) ≤ 0.582, while the worst case imbalance for the SLPT algorithm is (p - 1)/(p + 1) < 1. The SLPT bound is equal to the bound for a previously published algorithm while the LPTMH bound is the best known so far. Both LPTMH and SLPT take much less running time than competing algorithms. Results of experiments show that the SLPT algorithm performs better on the average than the LPTMH algorithm and as well as other known algorithms. © 1992.