On Preemption and Learning in Stochastic Scheduling

Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, Vianney Perchet
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:24478-24516, 2023.

Abstract

We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-merlis23a, title = {On Preemption and Learning in Stochastic Scheduling}, author = {Merlis, Nadav and Richard, Hugo and Sentenac, Flore and Odic, Corentin and Molina, Mathieu and Perchet, Vianney}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {24478--24516}, 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/merlis23a/merlis23a.pdf}, url = {https://proceedings.mlr.press/v202/merlis23a.html}, abstract = {We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.} }
Endnote
%0 Conference Paper %T On Preemption and Learning in Stochastic Scheduling %A Nadav Merlis %A Hugo Richard %A Flore Sentenac %A Corentin Odic %A Mathieu Molina %A Vianney Perchet %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-merlis23a %I PMLR %P 24478--24516 %U https://proceedings.mlr.press/v202/merlis23a.html %V 202 %X We study single-machine scheduling of jobs, each belonging to a job type that determines its duration distribution. We start by analyzing the scenario where the type characteristics are known and then move to two learning scenarios where the types are unknown: non-preemptive problems, where each started job must be completed before moving to another job; and preemptive problems, where job execution can be paused in the favor of moving to a different job. In both cases, we design algorithms that achieve sublinear excess cost, compared to the performance with known types, and prove lower bounds for the non-preemptive case. Notably, we demonstrate, both theoretically and through simulations, how preemptive algorithms can greatly outperform non-preemptive ones when the durations of different job types are far from one another, a phenomenon that does not occur when the type durations are known.
APA
Merlis, N., Richard, H., Sentenac, F., Odic, C., Molina, M. & Perchet, V.. (2023). On Preemption and Learning in Stochastic Scheduling. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:24478-24516 Available from https://proceedings.mlr.press/v202/merlis23a.html.

Related Material