mlsanityData to 7 Oct 2026

Scheduling with Predictions and the Price of Misprediction

arXiv 1902.00732 ↗First posted 2 Feb 2019cs.DScited by 45

Not on the map. Why?

Abstract (arXiv)

In many traditional job scheduling settings, it is assumed that one knows the time it will take for a job to complete service. In such cases, strategies such as shortest job first can be used to improve performance in terms of measures such as the average time a job waits in the system. We consider the setting where the service time is not known, but is predicted by for example a machine learning algorithm. Our main result is the derivation, under natural assumptions, of formulae for the performance of several strategies for queueing systems that use predictions for service times in order to schedule jobs. As part of our analysis, we suggest the framework of the "price of misprediction," which offers a measure of the cost of using predicted information.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 12; 2023: 8; 2024: 6; 2025: 5; 2026: 5.

45 papers.

Sort:

By area:

  1. 2021Learning to Optimize: A Primer and A Benchmarkcited by 206
  2. 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 34
  3. 2022Permutation Predictions for Non-Clairvoyant Schedulingcited by 22
  4. 2022Online Algorithms with Multiple Predictionscited by 22
  5. 2022Customizing ML Predictions for Online Algorithmscited by 21
  6. 2022Triangle and Four Cycle Counting with Predictions in Graph Streamscited by 20
  7. 2021A Novel Prediction Setup for Online Speed-Scalingcited by 17
  8. 2022A Universal Error Measure for Input Predictions Applied to Online Graph Problemscited by 14
  9. 2023Sorting with Predictionscited by 14
  10. 2021Can Q-Learning be Improved with Advice?cited by 13
  11. 2022A Regression Approach to Learning-Augmented Online Algorithmscited by 12
  12. 2021(Optimal) Online Bipartite Matching with Degree Informationcited by 11
33 more
  1. 2021Logarithmic Regret from Sublinear Hintscited by 11
  2. 2021Double Coverage with Machine-Learned Advicecited by 10
  3. 2021Robustification of Online Graph Exploration Methodscited by 10
  4. 2022Smoothed Online Optimization with Unreliable Predictionscited by 10
  5. 2023Improved Frequency Estimation Algorithms with and without Predictionscited by 10
  6. 2022Learning-Augmented Algorithms for Online TSP on the Linecited by 8
  7. 2024Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithmscited by 8
  8. 2022Scheduling with Speed Predictionscited by 6
  9. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  10. 2022Contextual Pandora's Boxcited by 5
  11. 2023Online Dynamic Acknowledgement with Learned Predictionscited by 4
  12. 2025Queueing, Predictions, and LLMs: Challenges and Open Problemscited by 4
  13. 2021Online Capacity Scaling Augmented With Unreliable Machine Learning Predictionscited by 3
  14. 2021Online Primal-Dual Algorithms with Predictions for Packing Problemscited by 3
  15. 2022Scheduling with Predictionscited by 3
  16. 2023Learning-Augmented Online Packet Scheduling with Deadlinescited by 3
  17. 2024SkipPredict: When to Invest in Predictions for Schedulingcited by 3
  18. 2023Sorting and Hypergraph Orientation under Uncertainty with Predictionscited by 2
  19. 2023On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rentalcited by 2
  20. 2024Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problemscited by 2
  21. 2023Online Resource Allocation: Bandits feedback and Advice on Time-varying Demandscited by 1
  22. 2023Online Covering with Multiple Expertscited by 1
  23. 2024Credence: Augmenting Datacenter Switch Buffer Sharing with ML Predictionscited by 1
  24. 2024Energy-Efficient Scheduling with Predictionscited by 1
  25. 2025Learning-Augmented Algorithms for Boolean Satisfiabilitycited by 1
  26. 2025Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approachcited by 1
  27. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  28. 2025Privacy-Preserving Learning-Augmented Data Structurescited by 0
  29. 2025A Switching Framework for Online Interval Scheduling with Predictionscited by 0
  30. 2026Learning-Augmented Online Scheduling with Parsimonious Preemptioncited by 0
  31. 2026OUTLETS: Output-Length Prediction from Speculative Decoding Backbonescited by 0
  32. 2026Augmented Hypothesis Testing with Persona-Based LLM Simulationscited by 0
  33. 2026Robust Non-Clairvoyant Scheduling with Classification Modelscited by 0