工件具有相似加工时长时两台机上LPT算法的性能分析
Performance Analysis of LPT Algorithm for Jobs with Similar Sizes on Two Machines
DOI: 10.12677/CSA.2019.97147, PDF,    国家自然科学基金支持
作者: 王 凤, 李荣珩*：湖南师范大学数学与统计学院，计算与随机数学教育部重点实验室，湖南 长沙；周云霞：湖南师范大学信息科学与工程学院，湖南 长沙
关键词: 排序问题；平行机；LPT算法；最坏性能比；Scheduling Problem； Identical Machine； LPT Algorithm； Worst Performance Ratio
摘要: 本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列L={J1,J2,...,Jn}中的工件满足pj∈[1,r](r≥1)，证明了LPT算法的最坏性能比为r的分段线性函数，此结论改进了已有的最好结论，并且是不能再改进的最好结论。
Abstract: 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={J1,J2,...,Jn} satisfies pj∈[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.
文章引用：王凤, 李荣珩, 周云霞. 工件具有相似加工时长时两台机上LPT算法的性能分析[J]. 计算机科学与应用, 2019, 9(7): 1309-1316. https://doi.org/10.12677/CSA.2019.97147

参考文献

[1] Graham, R.L. (1969) Bounds on Multiprocessing Timing Anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[5] He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[9] He, Y. and Zhang, G. (1999) Semi On-Line Scheduling on Two Identical Machines. Computing, 62, 179-187. [Google Scholar] [CrossRef] 
[10] Kellerer, H. (1991) Bounds for Non-Preemptive Scheduling Jobs with Similar Processing Times on Multiprocessor Systems Using LPT-Algorithm. Computing, 46, 183-191. [Google Scholar] [CrossRef]