How much can lookahead help in online single machine scheduling

This paper studies online single machine scheduling where jobs have unit length and the objective is to maximize the number of completed jobs. Lookahead is considered to improve the competitiveness of online deterministic strategies. For preemption-restart model, we will prove a lower bound of (⌊ LD ⌋ + 2) / (⌊ LD ⌋ + 1) for the case where LD ≥ 1 and 3/2 for the case where 0 ≤ LD < 1, in which LD is the length of time segment that online strategies can foresee at any time. For non-preemptive model, we mainly present a greedy strategy that has an optimal competitive ratio of 3/2 when 1 ≤ LD < 2 while its competitive ratio is bounded from above by 4/3 as LD goes larger.