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

• DOI: 10.1016/j.tcs.2014.02.015
• Publication Date: 2014-02-22T11:01:46Z
• Authors: Yong Wu; T.C.E. Cheng; Min Ji
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

Abstract 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 + 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 α-competitive ratio, where α ≈ 2.48119 is the largest root of the equation x 3 − 2 x 2 − 2 x + 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.