A better semi-online algorithm for Q3/s = s≤ s/C with the known largest size.

This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by s the speed of each machine, j = 1, 2, 3. Assume 0 < s = s = r ≤ t = s, and let s = t/r be the speed ratio. An algorithm with competitive ratio $$\max \left\{ {2,\tfrac{{3s + 6}} {{s + 6}}} \right\}$$ is presented. We also show the lower bound is at least $$\max \left\{ {2,\tfrac{{3s}} {{s + 6}}} \right\}$$. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun. [ABSTRACT FROM AUTHOR]