Scheduling with Untrusted Predictions

Scheduling with Untrusted Predictions

Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, Fanny Pascual

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 4581-4587. https://doi.org/10.24963/ijcai.2022/636

Using machine-learned predictions to create algorithms with better approximation guarantees is a very fresh and active field. In this work, we study classic scheduling problems under the learning augmented setting. More specifically, we consider the problem of scheduling jobs with arbitrary release dates on a single machine and the problem of scheduling jobs with a common release date on multiple machines. Our objective is to minimize the sum of completion times. For both problems, we propose algorithms which use predictions for taking their decisions. Our algorithms are consistent -- i.e. when the predictions are accurate, the performances of our algorithms are close to those of an optimal offline algorithm--, and robust -- i.e. when the predictions are wrong, the performance of our algorithms are close to those of an online algorithm without predictions. In addition, we confirm the above theoretical bounds by conducting experimental evaluation comparing the proposed algorithms to the offline optimal ones for both the single and multiple machines settings.
Keywords:
Planning and Scheduling: Scheduling
Planning and Scheduling: Learning in Planning and Scheduling
Uncertainty in AI: Nonprobabilistic Models