Algorithms for handling skew in parallel task scheduling

Presents 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 P rocessing 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. Both LPTMH and SLPT take make 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. A concrete example of the PITS problem arises when the database join operation is parallelized. The join is an important but expensive operation in relational systems and significant improvements in response time may be attained by parallelizing the join