Back
 AM  Vol.10 No.11 , November 2019
LPT Algorithm for Jobs with Similar Sizes on Three Machines
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.
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.
References

[1]   Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429.
https://doi.org/10.1137/0117039

[2]   Cheng, T.C.E., Kellerer, H. and Kotov, V. (2012) Algorithms Better than LPT for Semi-Online Scheduling with Decreasing Processing Times. Operations Research Letters, 40, 349-352.
https://doi.org/10.1016/j.orl.2012.05.009

[3]   He, Y.G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159.
https://doi.org/10.1016/j.dam.2004.12.005

[4]   He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187.
https://doi.org/10.1007/s006070050020

[5]   Kellerer, H., Kotov, V., Speranza, M.G. and Tuza, Z. (1997) Semi On-Line Algorithms for the Partition Problem. Operations Research Letters, 21, 235-242.
https://doi.org/10.1016/S0167-6377(98)00005-4

[6]   Li, R.H. and Huang, H.C. (2007) List Scheduling for Jobs with Arbitrary Release Times and Similar Lengths. Journal of Scheduling, 10, 365-373.
https://doi.org/10.1007/s10951-007-0042-8

[7]   Lin, L. and Tan, Z. (2014) Inefficiency of Nash Equilibrium for Scheduling Games with Constrained Jobs: A Parametric Analysis. Theoretical Computer Science, 521, 123-134.
https://doi.org/10.1016/j.tcs.2013.11.012

[8]   He, Y. and Dosa, G. (2005) Semi-Online Scheduling Jobs with Tightly-Grouped Processing Times on Three Identical Machines. Discrete Applied Mathematics, 150, 140-159.
https://doi.org/10.1016/j.dam.2004.12.005

[9]   Kellerer, H. (1991) Bounds for Non-Preemptive Scheduling Jobs with Similar Processing Times on Multiprocessor Systems Using LPT-Algorithm. Computing, 46, 183-191.
https://doi.org/10.1007/BF02238297

[10]   Graham, R.L. (1976) Bounds on the Performance of Scheduling Algorithms, Computer and Job-Shop Scheduling Theory. John Wiley Sons, New York, 165-227.

 
 
Top