Non-clairvoyant Scheduling with Partial Predictions

Ziyad Benomar, Vianney Perchet
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:3506-3538, 2024.

Abstract

The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-benomar24a, title = {Non-clairvoyant Scheduling with Partial Predictions}, author = {Benomar, Ziyad and Perchet, Vianney}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {3506--3538}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/benomar24a/benomar24a.pdf}, url = {https://proceedings.mlr.press/v235/benomar24a.html}, abstract = {The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.} }
Endnote
%0 Conference Paper %T Non-clairvoyant Scheduling with Partial Predictions %A Ziyad Benomar %A Vianney Perchet %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-benomar24a %I PMLR %P 3506--3538 %U https://proceedings.mlr.press/v235/benomar24a.html %V 235 %X The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, we present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria, and revealing a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.
APA
Benomar, Z. & Perchet, V.. (2024). Non-clairvoyant Scheduling with Partial Predictions. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:3506-3538 Available from https://proceedings.mlr.press/v235/benomar24a.html.

Related Material