Harnessing Randomization in Learning-Augmented Contract Scheduling

Contract scheduling is a fundamental framework for systems that trade computation time for solution quality when the available running time is unknown. While deterministic contract schedules have been extensively studied, the benefits of randomization remain largely unexplored. In this work, we study randomized contract scheduling both in the classical, agnostic setting and in the presence of predictions. First, we settle the agnostic setting by proving a tight lower bound on the best-possible performance of a randomized schedule. We then address learning-augmented contract scheduling, where the scheduler receives a prediction of the interruption time. We characterize the consistency–robustness tradeoff by providing a lower bound and a randomized schedule with nearly matching guarantees. We further mitigate the brittleness inherent in consistency-optimized algorithms via smoothing, obtaining provably gradual degradation under prediction error at only a small cost in consistency. Finally, we give the first analysis of a general sequential learning game that uses historical prediction data to calibrate trust in subsequent predictions, and determine the appropriate smoothness. Our theoretical and experimental results demonstrate that randomization can significantly improve the performance of interruptible systems based on contract scheduling.