Document Open Access Logo

Scheduling with Predictions and the Price of Misprediction

Author Michael Mitzenmacher

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.14.pdf
  • Filesize: 447 kB
  • 18 pages

Document Identifiers

Author Details

Michael Mitzenmacher
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA

Funding

  • Mitzenmacher, Michael: This work was supported in part by NSF grants CCF-1563710 and CCF-1535795.

Cite AsGet BibTex

Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.14

Abstract

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Queueing theory
  • Theory of computation → Online algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • Queues
  • shortest remaining processing time
  • algorithms with predictions
  • scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. Google Scholar
  2. Eric Balkanski, Aviad Rubinstein, and Yaron Singer. The power of optimization from samples. In Advances in Neural Information Processing Systems, pages 4017-4025, 2016. Google Scholar
  3. Eric Balkanski, Aviad Rubinstein, and Yaron Singer. The limitations of optimization from samples. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1016-1027, 2017. Google Scholar
  4. Eric Balkanski and Yaron Singer. The sample complexity of optimizing a convex function. In Proceedings of the 30th Conference on Learning Theory, pages 275-301, 2017. Google Scholar
  5. Eric Balkanski and Yaron Singer. Approximation guarantees for adaptive sampling. In Proceedings of the 35th International Conference on Machine Learning, pages 393-402, 2018. Google Scholar
  6. Burton H Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970. Google Scholar
  7. Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):204-234, 1995. Google Scholar
  8. Matteo Dell'Amico, Damiano Carra, and Pietro Michiardi. PSBS: Practical size-based scheduling. IEEE Transactions on Computers, 65(7):2199-2212, 2015. Google Scholar
  9. Uriel Feige and Robert Krauthgamer. Finding and certifying a large hidden clique in a semirandom graph. Random Structures & Algorithms, 16(2):195-208, 2000. Google Scholar
  10. Natarajan Gautam. Analysis of queues: methods and applications. CRC Press, 2012. Google Scholar
  11. Mor Harchol-Balter. Task assignment with unknown duration. J. ACM, 49(2):260-288, 2002. Google Scholar
  12. Mor Harchol-Balter. Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press, 2013. Google Scholar
  13. Mor Harchol-Balter, Mark E Crovella, and Cristina D Murta. On choosing a task assignment policy for a distributed server system. Journal of Parallel and Distributed Computing, 59(2):204-228, 1999. Google Scholar
  14. Avinatan Hassidim and Yaron Singer. Submodular optimization under noise. In Proceedings of the 30th Conference on Learning Theory, pages 1069-1122, 2017. Google Scholar
  15. Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In International Conference on Learning Representations, 2019. Google Scholar
  16. Leonard Kleinrock. Queueing systems, volume 1. Wiley, New York, 1975. Google Scholar
  17. Leonard Kleinrock. Queueing systems, volume 2: Computer applications. Wiley, New York, 1976. Google Scholar
  18. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science, pages 404-413, 1999. Google Scholar
  19. Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504, 2018. Google Scholar
  20. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, pages 3302-3311, 2018. Google Scholar
  21. Michael Mitzenmacher. How useful is old information? IEEE Trans. Parallel Distrib. Syst., 11(1):6-20, 2000. Google Scholar
  22. Michael Mitzenmacher. The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst., 12(10):1094-1104, 2001. Google Scholar
  23. Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, pages 462-471, 2018. Google Scholar
  24. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  25. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems, pages 9684-9693, 2018. Google Scholar
  26. Nir Rosenfeld, Eric Balkanski, Amir Globerson, and Yaron Singer. Learning to optimize combinatorial functions. In Proceedings of the 35th International Conference on Machine Learning, pages 4371-4380, 2018. Google Scholar
  27. Tim Roughgarden. Beyond worst-case analysis. arXiv preprint, 2018. URL: http://arxiv.org/abs/1806.09817.
  28. Linus E Schrage and Louis W Miller. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research, 14(4):670-684, 1966. Google Scholar
  29. Ziv Scully and Mor Harchol-Balter. SOAP bubbles: Robust scheduling under adversarial noise. In Proceedings of the 56th Annual Allerton Conference on Communication, Control, and Computing, 2018. Google Scholar
  30. Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. SOAP: One clean analysis of all age-based scheduling policies. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(1):16, 2018. Google Scholar
  31. Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385-463, 2004. Google Scholar
  32. Adam Wierman and Misja Nuyens. Scheduling despite inexact job-size information. In ACM SIGMETRICS Performance Evaluation Review, volume 36 (1), pages 25-36, 2008. Google Scholar
  33. Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. SATzilla: portfolio-based algorithm selection for SAT. Journal of artificial intelligence research, 32:565-606, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact