Learning for Sustainable Online Scheduling with Competitive Fairness Guarantees
Pengfei Li, Nicolas Christianson, Jianyi Yang, Adam Wierman, Shaolei Ren · 2025
In this paper, we investigate an online scheduling problem with covering constraints, in which a decision-maker must make sequential scheduling decisions with incomplete future information while satisfying long-term constraints.The decision-maker seeks to optimize both efficiency and fairness, yet the lack of perfect future information in the online setting and the conflicting nature of these objectives poses a significant challenge.To address this, we propose a learning-augmented algorithm, called LCF, for a general class of covering-constrained online scheduling problems that seeks to optimize efficiency while maintaining a strict fairness guarantee against any specified fairness-oriented baseline algorithm.Specifically, we present a first-of-its-kind analysis of a learningaugmented algorithm with both a cost/efficiency guarantee as well as a (1 + 𝜆)-competitive fairness guarantee for any non-negative 𝜆.To illustrate the real-world applicability of LCF, we present a case study focused on the efficient scheduling of distributed large language model (LLM) training, showcasing its ability to optimize operational costs while adhering to strict covering and fairness constraints.