Semi-Online Hierarchical Scheduling on Two Machines for l_p-Norm Load Balancing

摘要

This paper investigates semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the lp-norm of the machines' loads. We consider two semi-online versions with knowing the total processing time T of all jobs, or knowing the total processing time T-i of the jobs of hierarchy i for i = 1, 2 in advance. For the two semi-online versions, the best possible online algorithms are designed with competitive ratios of phi* and (2(p)+ 4(p)/2(3)(p))(1/p), respectively, where phi* is the maximum value of the function phi(x) = ((x+ 1/2 (1-x))(p)+(1/2(1-x))(p)/x(p)+(1-x)(p))(1/p) in x is an element of[1/2, 1]. When p = infinity, our results cover the known results for minimizing the makespan.