Optimal algorithms for semi-online machine covering on two hierarchical machines

This paper investigates the semi-online machine covering problem on two hierarchical machines where the jobs are correspondingly classified into two hierarchical classes. The objective is to maximize the minimum machine load. We show that if we only know the size of the largest job, no algorithm with a bounded competitive ratio exists. So we consider the case where we know both the size and the class of the largest job. If we know the size of the largest job and that it belongs to the higher class, then an optimal algorithm with a (1 + root 2/2)-competitive ratio exists. If we know the size of the largest job and that it belongs to the lower class, we design an optimal algorithm with an a-competitive ratio, where alpha approximate to 2.48119 is the largest root of the equation x(3) -2x(2) - 2x + 2 = 0. For the case where the total size of all the jobs is known in advance, we show that the competitive ratio of an optimal algorithm is 2. (C) 2014 Elsevier B.V. All rights reserved.