Author(s)

Yajie Ma¹, Rongheng Li¹, Yunxia Zhou²

¹Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China.
²College of Information Science and Engineering, Hunan Normal University, Changsha, China.

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

Ma, Y. , Li, R. and Zhou, Y. (2019) LPT Algorithm for Jobs with Similar Sizes on Three Machines. Applied Mathematics, 10, 947-955. doi: 10.4236/am.2019.1011066.