Share This Article:

LPT Algorithm for Jobs with Similar Sizes on Three Machines

Full-Text HTML XML Download Download as PDF (Size:400KB) PP. 947-955
DOI: 10.4236/am.2019.1011066    104 Downloads   235 Views


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.

Cite this paper

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.

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.