Giorgio Lucarelli
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Giorgio Lucarelli has a total of 86 co-authors. Here are the top co-authors by number of shared publications:
Evripidis Bampis
15 shared publicationsIoannis Milis
11 shared publicationsDimitrios Letsios
Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271
10 shared publications- Imed Kacem
Université de Lorraine
7 shared publications - Ioannis Milis
Athens University of Economics and Business
6 shared publications Vangelis Th. Paschos
6 shared publications
Latest Publications
- 14 June 2026
- Published by Springer Nature
- p. 104-117
Machine Learning and Data Analysis Method for Predicting an Efficient Algorithm for Heterogeneous Multicore Scheduling
- 14 June 2026
- Published by Springer Nature
- p. 104-117
Machine Learning and Data Analysis Method for Predicting an Efficient Algorithm for Heterogeneous Multicore Scheduling
- Open Access
- 13 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 13 (1) , 1-20
Non-Clairvoyant Makespan Minimization Scheduling with Predictions
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.
- 13 February 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 13 (1) , 1-20
Open AccessNon-Clairvoyant Makespan Minimization Scheduling with Predictions
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.
- 2 January 2026
- Published by Springer Nature
- p. 159-170
Machine Learning for Characterizing the Tardiness Minimization Problem on a Single Machine
- 2 January 2026
- Published by Springer Nature
- p. 159-170
Machine Learning for Characterizing the Tardiness Minimization Problem on a Single Machine
- 26 August 2024
- Published by Springer Nature
- p. 343-356
Makespan Minimization for Scheduling on Heterogeneous Platforms with Precedence Constraints
- 26 August 2024
- Published by Springer Nature
- p. 343-356
Makespan Minimization for Scheduling on Heterogeneous Platforms with Precedence Constraints
- 5 July 2024
- Published by Springer Nature in Annals of Operations Research
- Vol. 351 (1) , 751-778
Min–max relative regret for scheduling to minimize maximum lateness
- 5 July 2024
- Published by Springer Nature in Annals of Operations Research
- Vol. 351 (1) , 751-778
Min–max relative regret for scheduling to minimize maximum lateness
- 3 June 2023
- Published by Springer Nature
- p. 49-61
Min-Max Relative Regret for Scheduling to Minimize Maximum Lateness
- 3 June 2023
- Published by Springer Nature
- p. 49-61
Min-Max Relative Regret for Scheduling to Minimize Maximum Lateness
- 1 August 2022
- Published by Springer Nature
- p. 253-267
Two-Agent Scheduling with Resource Augmentation on Multiple Machines
- 1 August 2022
- Published by Springer Nature
- p. 253-267
Two-Agent Scheduling with Resource Augmentation on Multiple Machines
- 22 February 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 43 (5) , 1602-1627
Exact algorithms for scheduling programs with shared tasks
- 22 February 2021
- Published by Springer Nature in Journal of Combinatorial Optimization
- Vol. 43 (5) , 1602-1627
Exact algorithms for scheduling programs with shared tasks
- Open Access
Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$, where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which $g$ is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints.Open AccessPrimal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we provide a framework of analysis that is derived by duality properties, does not rely on potential functions and is applicable to a variety of scheduling problems. A key ingredient in our approach is bypassing the need for "black-box" rounding of fractional solutions, which yields improved competitive ratios. We begin with an interpretation of Highest-Density-First (HDF) as a primal-dual algorithm, and a corresponding proof that HDF is optimal for total fractional weighted flow time (and thus scalable for the integral objective). Building upon the salient ideas of the proof, we show how to apply and extend this analysis to the more general problem of minimizing $\sum_j w_j g(F_j)$, where $w_j$ is the job weight, $F_j$ is the flow time and $g$ is a non-decreasing cost function. Among other results, we present improved competitive ratios for the setting in which $g$ is a concave function, and the setting of same-density jobs but general cost functions. We further apply our framework of analysis to online weighted completion time with general cost functions as well as scheduling under polyhedral constraints.