Bemali Wickramanayake, Zhipeng He, et al.
Knowledge-Based Systems
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.
Bemali Wickramanayake, Zhipeng He, et al.
Knowledge-Based Systems
Xiaoxiao Guo, Shiyu Chang, et al.
AAAI 2019
Els van Herreweghen, Uta Wille
USENIX Workshop on Smartcard Technology 1999
Yale Song, Zhen Wen, et al.
IJCAI 2013