Algorithms for handling skew in parallel task scheduling

Abstract

We present two new algorithms, the LPT-MinHeight (LPTMH) algorithm and the Split-LPT (SLPT) algorithm, for handling skew in parallel task scheduling. 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 SPLT 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 other 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.