Semi-online Scheduling with Lookahead

The knowledge of future partial information in the form of a lookahead to design efficient online algorithms is a theoretically-efficient and realistic approach to solving computational problems. Design and analysis of semi-online algorithms with extra-piece-of-information (EPI) as a new input parameter has gained the attention of the theoretical computer science community in the last couple of decades. Though competitive analysis is a pessimistic worst-case performance measure to analyze online algorithms, it has immense theoretical value in developing the foundation and advancing the state-of-the-art contributions in online and semi-online scheduling. In this paper, we study and explore the impact of lookahead as an EPI in the context of online scheduling in identical machine frameworks. We introduce a k-lookahead model and design improved competitive semi-online algorithms. For a 2-identical machine setting, we prove a lower bound of frac43 and design an optimal algorithm with a matching upper bound of frac43 on the competitive ratio. For a 3-identical machine setting, we show a lower bound of frac1511 and design a frac1611-competitive improved semi-online algorithm.