Standard

Non-Clairvoyant Makespan Minimization Scheduling with Predictions. / Bampis, Evripidis; Кононов, Александр Вениаминович; Lucarelli, Giorgio и др.

Leibniz International Proceedings in Informatics, LIPIcs. Том 283 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Том 283).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаяРецензирование

Harvard

Bampis, E, Кононов, АВ, Lucarelli, G & Pascual, F 2023, Non-Clairvoyant Makespan Minimization Scheduling with Predictions. в Leibniz International Proceedings in Informatics, LIPIcs. Том. 283, 9, Leibniz International Proceedings in Informatics, LIPIcs, Том. 283, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 34th International Symposium on Algorithms and Computation, Kyoto, Япония, 03.12.2023. https://doi.org/10.4230/LIPIcs.ISAAC.2023.9

APA

Bampis, E., Кононов, А. В., Lucarelli, G., & Pascual, F. (2023). Non-Clairvoyant Makespan Minimization Scheduling with Predictions. в Leibniz International Proceedings in Informatics, LIPIcs (Том 283). [9] (Leibniz International Proceedings in Informatics, LIPIcs; Том 283). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2023.9

Vancouver

Bampis E, Кононов АВ, Lucarelli G, Pascual F. Non-Clairvoyant Makespan Minimization Scheduling with Predictions. в Leibniz International Proceedings in Informatics, LIPIcs. Том 283. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 9. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ISAAC.2023.9

Author

Bampis, Evripidis ; Кононов, Александр Вениаминович ; Lucarelli, Giorgio и др. / Non-Clairvoyant Makespan Minimization Scheduling with Predictions. Leibniz International Proceedings in Informatics, LIPIcs. Том 283 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{5a02f1a0177447e0a0a2ee7214b7be01,
title = "Non-Clairvoyant Makespan Minimization Scheduling with Predictions",
abstract = "We revisit the classical non-clairvoyant problem of scheduling a set of n jobs on a set of m parallel identical machines where the processing time of a job is not known until the job finishes. Our objective is the minimization of the makespan, i.e., the date at which the last job terminates its execution. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness). We first consider the non-preemptive case and we devise lower bounds, as a function of the error of the prediction, for any deterministic learning-augmented algorithm. Then we analyze a variant of Longest Processing Time first (LPT) algorithm (with and without release dates) and we prove that it is consistent, smooth, and robust. Furthermore, we study the preemptive case and we provide lower bounds for any deterministic algorithm with predictions as a function of the prediction error. Finally, we introduce a variant of the classical Round Robin algorithm (RR), the Predicted Proportional Round Robin algorithm (PPRR), which we prove to be consistent, smooth and robust.",
keywords = "learning-augmented algorithm, online, scheduling",
author = "Evripidis Bampis and Кононов, {Александр Вениаминович} and Giorgio Lucarelli and Fanny Pascual",
note = "Funding Evripidis Bampis: This work was partially supported by the French National Research Agency (Algoridam ANR-19-CE48-0016). Alexander Kononov: This research was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019).; 34th International Symposium on Algorithms and Computation, ISAAC 2023 ; Conference date: 03-12-2023 Through 06-12-2023",
year = "2023",
month = dec,
doi = "10.4230/LIPIcs.ISAAC.2023.9",
language = "English",
isbn = "978-395977289-1",
volume = "283",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",
address = "Germany",

}

RIS

TY - GEN

T1 - Non-Clairvoyant Makespan Minimization Scheduling with Predictions

AU - Bampis, Evripidis

AU - Кононов, Александр Вениаминович

AU - Lucarelli, Giorgio

AU - Pascual, Fanny

N1 - Conference code: 34

PY - 2023/12

Y1 - 2023/12

N2 - We revisit the classical non-clairvoyant problem of scheduling a set of n jobs on a set of m parallel identical machines where the processing time of a job is not known until the job finishes. Our objective is the minimization of the makespan, i.e., the date at which the last job terminates its execution. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness). We first consider the non-preemptive case and we devise lower bounds, as a function of the error of the prediction, for any deterministic learning-augmented algorithm. Then we analyze a variant of Longest Processing Time first (LPT) algorithm (with and without release dates) and we prove that it is consistent, smooth, and robust. Furthermore, we study the preemptive case and we provide lower bounds for any deterministic algorithm with predictions as a function of the prediction error. Finally, we introduce a variant of the classical Round Robin algorithm (RR), the Predicted Proportional Round Robin algorithm (PPRR), which we prove to be consistent, smooth and robust.

AB - We revisit the classical non-clairvoyant problem of scheduling a set of n jobs on a set of m parallel identical machines where the processing time of a job is not known until the job finishes. Our objective is the minimization of the makespan, i.e., the date at which the last job terminates its execution. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness). We first consider the non-preemptive case and we devise lower bounds, as a function of the error of the prediction, for any deterministic learning-augmented algorithm. Then we analyze a variant of Longest Processing Time first (LPT) algorithm (with and without release dates) and we prove that it is consistent, smooth, and robust. Furthermore, we study the preemptive case and we provide lower bounds for any deterministic algorithm with predictions as a function of the prediction error. Finally, we introduce a variant of the classical Round Robin algorithm (RR), the Predicted Proportional Round Robin algorithm (PPRR), which we prove to be consistent, smooth and robust.

KW - learning-augmented algorithm

KW - online

KW - scheduling

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85179131991&origin=inward&txGid=053c894a99a86df633cb673571904538

UR - https://www.mendeley.com/catalogue/20eb4734-dda3-3682-bf55-a92eb6ae505e/

U2 - 10.4230/LIPIcs.ISAAC.2023.9

DO - 10.4230/LIPIcs.ISAAC.2023.9

M3 - Conference contribution

SN - 978-395977289-1

VL - 283

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Leibniz International Proceedings in Informatics, LIPIcs

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 34th International Symposium on Algorithms and Computation

Y2 - 3 December 2023 through 6 December 2023

ER -

ID: 59356328