Research ArticleOpen AccessGoogle Scholar indexed
<i>LPT</i> Algorithm for Jobs with Similar Sizes on Three Machines
Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China
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
- 1 Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China
- 2 Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, China
- 3 College of Information Science and Engineering, Hunan Normal University, Changsha, China
Applied Mathematics·Volume 10 (2019)·Pages 947–955·Published 24 October 2019·DOI10.4236/am.2019.1011066
Copy link · social · email
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.
Keywords<i>LPT</i>AlgorithmParallel MachinePerformance RatioSchedule
- Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. https://doi.org/10.1137/0117039
- 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
- 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
- He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
- 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
- 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
- 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
- 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
- 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
- Graham, R.L. (1976) Bounds on the Performance of Scheduling Algorithms, Computer and Job-Shop Scheduling Theory. John Wiley Sons, New York, 165-227.