科研之友
微信
新浪微博
Facebook
分享链接
摘要
This paper studies online hierarchical scheduling on two uniform machines with the objective to minimize makespan. Machines are provided with different capability, i.e., the one with speed s can schedule all jobs, while the other one with speed 1 can only process partial jobs. Optimal algorithms for any 0 < s < infinity are given in the paper. For 0 < s < 1, it has a competitive ratio of min{1 + s, 1 + 1+s/1+s+s(2)}. For s > 1, the competitive ratio is min {1+s/s, 1 + 2s/1+s+s(2)}.
- 出版日期2010-7
- 单位浙江大学
