Semi-online scheduling with combined information on two identical machines in parallel

详细信息    查看全文

• 作者：Qian Cao ; Guohua Wan
• 关键词：Scheduling ; Semi ; online ; Identical parallel machines ; Combined information
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：686-695
• 全文大小：488 KB
• 参考文献：Cao Q, Liu ZH, Cheng TCE (2011) Semi-online scheduling with known partial information about job sizes on two identical machines. Theoret Comput Sci 412(29):3731–3737MathSciNet CrossRef MATH
  Epstein L (2003) Bin stretching revisited. Acta Informatica 39:97–117MathSciNet CrossRef MATH
  Faigle U, Kern W, Turan G (1989) On the performance of online algorithms for partition problems. Acta Cybernetica 9:107–119MathSciNet MATH
  Graham RL (1966) Bounds for certain multiprocessor anomalies. Bell Syst Techn J 45:1563–1581CrossRef
  He Y, Zhang G (1999) Semi on-line scheduling on two identical machines. Computing 62:179–187MathSciNet CrossRef MATH
  Pinedo ML (2012) Scheduling: theory, algorithms, and systems, 4th edn. Springer, BerlinCrossRef
  Seiden S, Sgall J, Woeginger G (2000) Semi-online scheduling with decreasing job sizes. Oper Res Lett 27:215–227MathSciNet CrossRef
  Tan ZY, He Y (2002) Semi-on-line problems on two identical machines with combined partial information. Oper Res Lett 30:408–414MathSciNet CrossRef MATH
  
• 作者单位：Qian Cao (1) (2)
  Guohua Wan (2)
  
  1. College of Economics and Management, Shanghai University of Electric Power, Shanghai, China
  2. Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

This paper is concerned with a semi-online scheduling problem with combined information on two identical parallel machines to minimize the makespan, where all the jobs have processing times in the interval \([1,\,t]\)  \((t\ge 1)\) and the jobs arrive in non-increasing order of their processing times. The objective is to minimize the makespan. For \(t\ge 1\), we obtain a lower bound \(\max _{N=1,2,3,\ldots }\left\{ \min \{\frac{4N+3}{4N+2}\,,\frac{Nt+N+1}{2N+1}\}\right\} \) and show that the competitive ratio of the \(LS\) algorithm achieves the lower bound. Keywords Scheduling Semi-online Identical parallel machines Combined information