Competitive Fair Scheduling with Predictions

Beyond the worst-case analysis of algorithms, the learning-augmented framework considers that an algorithm can leverage possibly imperfect predictions about the unknown variables to have guarantees tied to the prediction quality. We consider online non-clairvoyant scheduling to minimize the max-stretch under this framework, where the scheduler can access job size predictions. We present a family of algorithms: Relaxed-Greedy (RG) with an O(η 3 • √ P ) competitive ratio, where η denotes the prediction error for job sizes and P the maximum job size ratio; Adaptive Relaxed-Greedy with an O(λ 0.5 • η 2.5 • √ P ) competitive ratio, where λ denotes the error for the minimum job size; Predictive Relaxed-Greedy with an O(λ 0.5 • φ 0.5 • η • maxη, φ • √ P ) competitive ratio, where φ denotes the error for the maximum job size. We also present RG x , an algorithm that represents a tradeoff between consistency and smoothness, with an O(η 2+2x • P 1-x ) competitive ratio. We introduce a general method using resource augmentation to bound robustness, resulting in RR-augmented RG, with a (1 + ϵ)-speed O(minη 3 √ P , n ϵ ) competitive ratio. Finally, we conduct simulations on synthetic and real-world datasets to evaluate the practical performance of these algorithms.