Semi-online Scheduling with Look-Ahead
摘要
The availability of partial future information can significantly improve the design of online algorithms for scheduling. In this work, we study the role of lookahead as an extra piece of information (EPI) in semi-online scheduling of jobs on identical machines with the makespan minimization objective. While competitive analysis remains the standard tool to evaluate online algorithms, incorporating lookahead raises fundamental questions about achievable bounds on the competitive ratio. We introduce the k-lookahead semi-online scheduling model, where the processing times of the next k jobs are known when scheduling the current one. For the two-machine setting, we prove a lower bound of 4/3 on the competitive ratio and design a deterministic semi-online algorithm with 1-lookahead that matches this bound, showing that increasing the lookahead size beyond one does not yield further improvement. For the three-machine setting, we establish a lower bound of 15/11 and propose a 1-lookahead algorithm achieving an upper bound of 16/11, thus improving upon the best-known competitive ratio of 5/3 for classical online scheduling. Our results provide the first tight characterization of lookahead-based semi-online scheduling on two machines and significantly advance the known bounds for three machines, demonstrating the practical and theoretical impact of the lookahead model.