What is it about?
We use machine learning to predict every job size and use them to help with scheduling. We prove an upper bound of algorithm performance under arbitrary bad predictions. Our algorithm achieves the bound outperforming the state-of-the-art algorithm without job size predictions.
Featured Image
Why is it important?
The learning-augmented algorithm is an emerging field. We want to have an algorithm which uses machine learning predictions and has its performance depends on the prediction quality. Specifically, we want the algorithm to perform well if the predictions are accurate (consistency) and perform bounded if the predictions are bad (robustness). To this end, we give the first sufficient condition for any algorithm to achieve a bounded performance under any predictions. We also design an algorithm that is consistent and robust to the predictions. The algorithm is proven to have the optimal robustness under bad predictions.
Perspectives
In the real world, precise job sizes are inaccessible in scheduling. No-clairvoyant algorithms are the standard solutions to this issue, which do not assume any information about the job sizes. The age assumption of unknown job sizes is going unrealistic. Machine learning nowadays provides more accurate predictions and can give us more information about job size. Thus, learning-augmented algorithms will be the future direction of no-clairvoyant scheduling. We hope this paper can inform people about the new scheduling method.
Chunhao Li
University of Sydney
Read the Original
This page is a summary of: Brief Announcement, July 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3490148.3538557.
You can read the full text:
Contributors
The following have contributed to this page
