Semi-online scheduling on two uniform parallel machines with initial lookahead

This work studies the problem of semi-online scheduling on two uniform parallel machines with speeds 1 and s (≥2), respectively. We introduce a novel concept of initial lookahead in which any deterministic online algorithm has the full knowledge of the first k jobs at the beginning, while the remaining jobs are released one-by-one in the online over-list mode. The objective of the considered problem is to minimize the makespan. We focus on the case where the first k jobs are of a total processing time not less than ( s + 1)Δ where Δ is the largest job length, and it is assumed that s is an integer. We prove a lower bound of ( s 2 + s +1)/( s 2 + s ) , and propose a deterministic semi-online algorithm with competitive ratio of ( s +1) 2 / s 2 + s +1. The ratio is at most 9/7 and much less than that of 1.618 for the corresponding case without initial lookahead (Cho and Sahni, SIAM J. Comput . 9 (1980) 91–103). Our results demonstrate that a finite ability of initial lookahead can greatly improve the competitiveness of online algorithms.