Contract Scheduling with Distributional and Multiple Advice

Contract Scheduling with Distributional and Multiple Advice

Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, Bertrand Simon

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence
Main Track. Pages 3652-3660. https://doi.org/10.24963/ijcai.2024/404

Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice.
Keywords:
Machine Learning: ML: Optimization
Planning and Scheduling: PS: Scheduling
Planning and Scheduling: PS: Learning in planning and scheduling
Uncertainty in AI: UAI: Sequential decision making