Optimal online algorithms on two hierarchical machines with tightly-grouped processing times

详细信息    查看全文

• 作者：An Zhang (1)
  Yiwei Jiang (2)
  Lidan Fan (3)
  Jueliang Hu (4)
  
  1. Institute of Operational Research and Cybernetics ; Hangzhou Dianzi University ; Hangzhou ; 聽310018 ; People鈥檚 Republic of China
  2. Department of Mathematics ; Zhejiang Sci-Tech University ; Hangzhou ; 聽310018 ; People鈥檚 Republic of China
  3. Department of Computer Science ; The University of Texas at Dallas ; Dallas ; TX ; 75080 ; USA
  4. School of Science ; Zhejiang Sci-Tech University ; Hangzhou ; 310018 ; People鈥檚 Republic of China
  
• 关键词：Online scheduling ; Hierarchy ; Competitive ratio
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：29
• 期：4
• 页码：781-795
• 全文大小：194 KB
• 参考文献：1. Bar-Noy, A, Freund, A, Naor, J (2001) On-line load balancing in a hierarchical server topology. SIAM Journal on Computing. 31: pp. 527-549 CrossRef
  2. Chassid, O, Epstein, L (2008) The hierarchical model for load balancing on two machines. Journal of Combinatorial Optimization. 15: pp. 305-314 CrossRef
  3. Crescenzi, P, Gambosi, G, Penna, P (2004) On-line algorithms for the channel assignment problem in cellular networks. Discrete Applied Mathematics. 137: pp. 237-266 CrossRef
  4. D贸sa, G, Epstein, L (2008) Preemptive scheduling on a small number of hierarchical machines. Information and Computation. 206: pp. 602-619 CrossRef
  5. He, Y, Zhang, G (1999) Semi on-line scheduling on two identical machines. Computing. 62: pp. 179-187 CrossRef
  6. Jiang, Y (2008) Online scheduling on parallel machines with two GoS levels. Journal of Combinatorial Optimization. 16: pp. 28-38 CrossRef
  7. Jiang, Y, He, Y, Tang, C (2006) Optimal online algorithms for scheduling on two identical machines under a grade of service. Journal of Zhejiang University Science. 7A: pp. 309-314 CrossRef
  8. Liu, M, Chu, C, Xu, Y, Zheng, F (2011) Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times. Journal of Combinatorial Optimization. 21: pp. 138-149 CrossRef
  9. Park, J, Chang, S, Lee, K (2006) Online and semi-online scheduling of two machines under a grade of service provision. Operations Research Letters. 34: pp. 692-696 CrossRef
  10. Tan, Z, Zhang, A (2010) A note on hierarchical scheduling on two uniform machines. Journal of Combinatorial Optimization. 20: pp. 85-95 CrossRef
  11. Tan, Z, Zhang, A (2011) Online hierarchical scheduling: An approach using mathematical programming. Theoretical Computer Science. 412: pp. 246-256 CrossRef
  12. Wu, Y, Ji, M, Yang, Q (2012) Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision. International Journal of Production Economics. 135: pp. 367-371 CrossRef
  13. Zhang, A, Jiang, Y, Tan, Z (2009) Online parallel machines scheduling with two hierarchies. Theoretical Computer Science. 410: pp. 3597-3605 CrossRef
  
• 刊物类别：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 considers an online hierarchical scheduling problem on two parallel identical machines. The objective is to minimize the makspan. It is assumed that all jobs have bounded processing times in between \(p\) and \(rp\) , where \(p>0\) and \(r\ge 1\) . We first improve a previous result by giving an optimal online algorithm for the non-preemptive version. For the preemptive version, we present an optimal preemptive algorithm without introducing idle time for all \(r\ge 1\) . If the algorithm is allowed to use idle time, we show that the semi-online information that jobs are tightly-grouped cannot help improve the bound of the pure online problem.