TITLE:
LPT Algorithm for Jobs with Similar Sizes on Three Machines
AUTHORS:
Yajie Ma, Rongheng Li, Yunxia Zhou
KEYWORDS:
LPT Algorithm, Parallel Machine, Performance Ratio, Schedule
JOURNAL NAME:
Applied Mathematics,
Vol.10 No.11,
November
11,
2019
ABSTRACT: 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.