<i>LPT</i>Algorithm for Jobs with Similar Sizes on Three Machines  

作　　者：Yajie Ma[1] Rongheng Li[1] Yunxia Zhou[1] 

出　　处：《Applied Mathematics》2019年第11期947-955,共9页应用数学（英文）

摘　　要：In this paper, LPT (largest processing time) algorithm is considered for scheduling jobs with similar sizes on three machines. The objective function is to minimize the maximum completion time of all machines. The worst case performance ratio of the LPT algorithm is given as a piecewise linear function of r if job sizes fall in [1, r]. Our result is better than the existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.In this paper, LPT (largest processing time) algorithm is considered for scheduling jobs with similar sizes on three machines. The objective function is to minimize the maximum completion time of all machines. The worst case performance ratio of the LPT algorithm is given as a piecewise linear function of r if job sizes fall in [1, r]. Our result is better than the existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.

关 键 词：LPT ALGORITHM Parallel Machine Performance Ratio SCHEDULE 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]