A note on hierarchical scheduling on two uniform machines

Research paper by Zhiyi Tan, An Zhang

Indexed on: 19 Nov '08Published on: 19 Nov '08Published in: Journal of Combinatorial Optimization

Abstract

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<∞ are given in the paper. For 0<s<1, it has a competitive ratio of $$\min\{1+s,1+\frac{1+s}{1+s+s^{2}}\}$$ . For s>1, the competitive ratio is $$\min\{\frac{1+s}{s},1+\frac{2s}{1+s+s^{2}}\}$$ .