TY - JOUR

T1 - Non-Clairvoyant Makespan Minimization Scheduling with Predictions

AU - Bampis, Evripidis

AU - Kononov, Alexander

AU - Lucarelli, Giorgio

AU - Pascual, Fanny

N1 - Non-Clairvoyant Makespan Minimization Scheduling with Predictions / E. Bampis, A. Kononov, G. Lucarelli, F. Pascual // ACM Transactions on Parallel Computing. – 2025. – P. 3777410. – DOI 10.1145/3777410. – EDN FMJWLU. Evripidis Bampis was partially supported by the French National Research Agency (Algoridam ANR-19-CE48-0016).The research of Alexander Kononov was carried out within the framework of the state contract of the Sobolev Institute ofMathematics (project FWNF-2022-0019).

PY - 2026/2/13

Y1 - 2026/2/13

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 the Longest Processing Time first 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, the Predicted Proportional Round Robin algorithm, 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 the Longest Processing Time first 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, the Predicted Proportional Round Robin algorithm, which we prove to be consistent, smooth, and robust.

KW - Non-clairvoyant scheduling

KW - machine learning predictions

KW - makespan

UR - https://www.scopus.com/pages/publications/105031890281

UR - https://www.elibrary.ru/item.asp?id=87123077

UR - https://www.mendeley.com/catalogue/6d70257b-bb45-3853-b726-eafc6306a239/

U2 - 10.1145/3777410

DO - 10.1145/3777410

M3 - Article

VL - 13

SP - 1

EP - 20

JO - ACM Transactions on Parallel Computing

JF - ACM Transactions on Parallel Computing

SN - 2329-4949

IS - 1

ER -