On-Line Scheduling on Parallel Machines to Minimize the Makespan

详细信息    查看全文

• 作者：Songsong Li ; Yuzhong Zhang
• 关键词：Lower bound ; on ; line algorithm ; scheduling
• 刊名：Journal of Systems Science and Complexity
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：29
• 期：2
• 页码：472-477
• 全文大小：149 KB
• 参考文献：[1]Graham R L, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 1966, 45(9): 1563–1581.CrossRef MATH
  [2]Epstein L, Noga J, Seiden S, et al., Randomized on-line scheduling on two uniform machines, Journal of Scheduling, 2001, 4(2): 71–92.MathSciNet CrossRef MATH
  [3]Li R and Huang H C, On-line scheduling for jobs with arbitrary release times, Computing, 2004, 73(1): 79–97.MathSciNet CrossRef MATH
  [4]Hall L A and Shmoys D B, Approximation schemes for constrained scheduling problems//Foundations of Computer Science, 1989, 30th Annual Symposium on IEEE, 1989, 134–139.
  [5]Shmoys D B, Wein J, and Williamson D P, Scheduling parallel machines on-line, SIAM Journal on Computing, 1995, 24(6): 1313–1331.MathSciNet CrossRef MATH
  [6]Graham R L, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, 1969, 17(2): 416–429.MathSciNet CrossRef MATH
  [7]Chen B and Vestjens A, Scheduling on identical machines: How good is LPT in an on-line setting?, Operations Research Letters, 1997, 21(4): 165–169.MathSciNet CrossRef MATH
  [8]Noga J and Seiden S S, An optimal online algorithm for scheduling two machines with release times, Theoretical Computer Science, 2001, 268(1): 133–143.MathSciNet CrossRef MATH
  
• 作者单位：Songsong Li (1)
  Yuzhong Zhang (1)
  
  1. School of Management, Qufu Normal University, Rizhao, 276826, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Systems Theory and Control
  Applied Mathematics and Computational Methods of Engineering
  Operations Research/Decision Theory
  Probability Theory and Stochastic Processes
  
• 出版者：Academy of Mathematics and Systems Science, Chinese Academy of Sciences, co-published with Springer
• ISSN：1559-7067

文摘

This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s (s ≥ 1), and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of (1 + \(\sqrt 5 \))/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of (15 − \(\sqrt {17} \))/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.