TY - GEN

T1 - Scheduling with Untrusted Predictions

AU - Bampis, Evripidis

AU - Dogeas, Konstantinos

AU - Kononov, Alexander

AU - Lucarelli, Giorgio

AU - Pascual, Fanny

N1 - Funding Information: This work was partially supported by the French National Research Agency (Energumen ANR-18-CE25-0008 and Algori-dam ANR-19-CE48-0016). The research of the third author was supported by the Russian Science Foundation RSF-ANR 21-41-09017. Publisher Copyright: © 2022 International Joint Conferences on Artificial Intelligence. All rights reserved.

PY - 2022

Y1 - 2022

N2 - 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 when making 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.

AB - 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 when making 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.

UR - http://www.scopus.com/inward/record.url?scp=85137923699&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85137923699

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 4581

EP - 4587

BT - Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022

A2 - De Raedt, Luc

PB - International Joint Conferences on Artificial Intelligence

T2 - 31st International Joint Conference on Artificial Intelligence, IJCAI 2022

Y2 - 23 July 2022 through 29 July 2022

ER -