Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints

Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, Jens Schlöter
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:18563-18583, 2023.

Abstract

We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed. Given strong impossibility results in classical competitive analysis, we investigate the problem in a learning-augmented setting, where an algorithm has access to predictions without any quality guarantee. We discuss different prediction models: novel problem-specific models as well as general ones, which have been proposed in previous works. We present lower bounds and algorithmic upper bounds for different precedence topologies, and thereby give a structured overview on which and how additional (possibly erroneous) information helps for designing better algorithms. Along the way, we also improve bounds on traditional competitive ratios for existing algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-lassota23a, title = {Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints}, author = {Lassota, Alexandra Anna and Lindermayr, Alexander and Megow, Nicole and Schl\"{o}ter, Jens}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {18563--18583}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/lassota23a/lassota23a.pdf}, url = {https://proceedings.mlr.press/v202/lassota23a.html}, abstract = {We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed. Given strong impossibility results in classical competitive analysis, we investigate the problem in a learning-augmented setting, where an algorithm has access to predictions without any quality guarantee. We discuss different prediction models: novel problem-specific models as well as general ones, which have been proposed in previous works. We present lower bounds and algorithmic upper bounds for different precedence topologies, and thereby give a structured overview on which and how additional (possibly erroneous) information helps for designing better algorithms. Along the way, we also improve bounds on traditional competitive ratios for existing algorithms.} }
Endnote
%0 Conference Paper %T Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints %A Alexandra Anna Lassota %A Alexander Lindermayr %A Nicole Megow %A Jens Schlöter %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-lassota23a %I PMLR %P 18563--18583 %U https://proceedings.mlr.press/v202/lassota23a.html %V 202 %X We consider non-clairvoyant scheduling with online precedence constraints, where an algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed. Given strong impossibility results in classical competitive analysis, we investigate the problem in a learning-augmented setting, where an algorithm has access to predictions without any quality guarantee. We discuss different prediction models: novel problem-specific models as well as general ones, which have been proposed in previous works. We present lower bounds and algorithmic upper bounds for different precedence topologies, and thereby give a structured overview on which and how additional (possibly erroneous) information helps for designing better algorithms. Along the way, we also improve bounds on traditional competitive ratios for existing algorithms.
APA
Lassota, A.A., Lindermayr, A., Megow, N. & Schlöter, J.. (2023). Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:18563-18583 Available from https://proceedings.mlr.press/v202/lassota23a.html.

Related Material