# Semi-online Scheduling with Lookahead

arXiv: https://arxiv.org/abs/2306.06003 · HTML: https://mlsanity.com/paper/2306.06003/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2023.

## Built on by (most cited first, 1 of 1)

- [A Note On Lookahead In Real Life And Computing](https://mlsanity.com/paper/2403.17942/) (2024)

## Abstract (arXiv)

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.