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 H1 with competitive ratio of s is optimal for 1.325≤s≤1+52 and s