工件具有相似加工时长时两台机上LPT算法的性能分析
Performance Analysis of LPT Algorithm for Jobs with Similar Sizes on Two Machines

DOI: 10.12677/CSA.2019.97147, PP. 1309-1316

Keywords: 排序问题，平行机，LPT算法，最坏性能比
Scheduling Problem, Identical Machine, LPT Algorithm, Worst Performance Ratio

Full-Text   Cite this paper   Add to My Lib

Abstract:

本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列L={J₁,J₂,...,J_n}中的工件满足p_j∈[1,r](r≥1)，证明了LPT算法的最坏性能比为r的分段线性函数，此结论改进了已有的最好结论，并且是不能再改进的最好结论。
In this paper, LPT algorithm is considered for the scheduling problem in which the processing times of jobs are similar on two machines. The objective function is to minimize the maximum completion time of all machines. The worst performance ratio of the LPT algorithm is given as a piecewise linear function of r if job list L={J₁,J₂,...,J_n} satisfies p_j∈[1,r](r≥1). Our result improves the best existing result. Furthermore, the ratio given here is the best. That means our result cannot be improved any more.

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]	Graham, R.L. (1976) Bounds on the Performance of Scheduling Algorithms. In: Coffmann, E.G., Ed., Computer and Job-Shop Scheduling Theory, John Wiley Sons, New York, 165-227.
[3]	Cheng, T.C.E., Kellerer, H. and Kotov, V. (2012) Algorithms Better than LPT for Semi-Online Schedul-ing with Decreasing Processing Times. Operations Research Letters, 40, 349-352. https://doi.org/10.1016/j.orl.2012.05.009
[4]	He, Y. and Dòsa, 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
[5]	He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
[6]	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
[7]	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
[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
[9]	He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. https://doi.org/10.1007/s006070050020
[10]	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

Full-Text