Semi-online scheduling with bounded job sizes on two uniform machines

In this paper, we investigate a semi-online scheduling problem on two uniform machines with the speed ratio s. It is assumed that all jobs have their processing times between p and tp ( p 0, t 1 ). The objective is to minimize the makespan. We give the competitive ratio of LS algorithm which is a piecewise function on t 1 and s 1 . It shows that LS is an optimal algorithm for most regions on s and t. We further present two optimal algorithms. The algorithm H 1 with competitive ratio of s is optimal for 1.325 s 1 + 5 2 and s < t s 2 - 1 1 + s - s 2 . The algorithm H 2 with competitive ratio of s is optimal for 1.206 s 1.5 and s t min { 2 s - 1, 2 ( s 2 - 1 ) 1 + s - s 2 }, and it is also optimal for 1 s 1 + 17 4 and max { 2 s - 1, - s + 9 s 2 + 8 s 2 s } t 2 s with competitive ratio of 1 + t 2 .