Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Scheduling with Untrusted Predictions. / Bampis, Evripidis; Dogeas, Konstantinos; Kononov, Alexander et al.
Proceedings of the 31st International Joint Conference on Artificial Intelligence, IJCAI 2022. ed. / Luc De Raedt. International Joint Conferences on Artificial Intelligence, 2022. p. 4581-4587 (IJCAI International Joint Conference on Artificial Intelligence).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
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 -
ID: 38050591