Document Open Access Logo

Distortion-Oblivious Algorithms for Scheduling on Multiple Machines

Authors Yossi Azar, Eldad Peretz, Noam Touitou

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.16.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Author Details

Yossi Azar
  • Tel Aviv University, Israel
Eldad Peretz
  • Tel Aviv University, Israel
Noam Touitou
  • Tel Aviv University, Israel
  • Amazon, Tel Aviv, Israel

Funding

  • Azar, Yossi: Supported in part by the Israel Science Foundation (grant No. 2304/20).

Cite As Get BibTex

Yossi Azar, Eldad Peretz, and Noam Touitou. Distortion-Oblivious Algorithms for Scheduling on Multiple Machines. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.16

Abstract

We consider the classic online problem of scheduling on multiple machines to minimize total flow time and total stretch where the input consists of estimates on the processing time provided for each job once released. The performance of such algorithms should depend on μ, the error in the estimates of the processing time for that instance (such an algorithm is called a distortion oblivious algorithm). Previously, a distortion oblivious algorithm to minimize flow time was provided only for a single machine. In this paper we extend the work to multiple machines and also consider the total stretch objective. In particular, we design a non-migrative distortion oblivious algorithm to minimize total flow time with a competitive ratio of O(μ log P), where P is the ratio between the maximum to minimum processing time. We show that with immediate-dispatching one cannot achieve a competitive ratio which is a function of μ and P; moreover, a competitive ratio which is sub-polynomial in the number of jobs is also impossible. We also present the first distortion-oblivious algorithm for minimizing the stretch time, both on a single and on multiple machines. The competitive ratio of these algorithms are O(μ²) which is optimal as we also prove a matching Ω(μ²) lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online
  • Scheduling
  • Predictions
  • Stretch
  • Flow Time

Metrics

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

References

  1. Algorithms with predictions. URL: https://algorithms-with-predictions.github.io.
  2. Nir Avrahami and Yossi Azar. Minimizing total flow time and total completion time with immediate dispatching. In Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '03, pages 11-18, New York, NY, USA, 2003. ACM. URL: https://doi.org/10.1145/777412.777415.
  3. Baruch Awerbuch, Yossi Azar, Stefano Leonardi, and Oded Regev. Minimizing the flow time without migration. SIAM Journal on Computing, 31(5):1370-1382, 2002. URL: https://doi.org/10.1137/S009753970037446X.
  4. Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1070-1080. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451023.
  5. Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for minimizing flow time. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 252-274. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.13.
  6. Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions, 2022. URL: https://doi.org/10.48550/ARXIV.2205.01247.
  7. Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, and Amitabh Sinha. Non-clairvoyant scheduling for minimizing mean slowdown. Algorithmica, 40(4):305-318, 2004. URL: https://doi.org/10.1007/s00453-004-1115-0.
  8. Luca Becchetti and Stefano Leonardi. Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 94-103, 2001. Google Scholar
  9. Chandra Chekuri, Sanjeev Khanna, and An Zhu. Algorithms for minimizing weighted flow time. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 84-93, 2001. URL: https://doi.org/10.1145/380752.380778.
  10. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. Journal of the ACM (JACM), 65(1):1-33, 2017. Google Scholar
  11. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 531-540. IEEE, 2014. Google Scholar
  12. Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '21, pages 285-294, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3409964.3461790.
  13. Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, New Orleans, LA, USA, January 5 - 8, 2020., 2020. Google Scholar
  14. Stefano Leonardi. A Simpler Proof of Preemptive Total Flow Time Approximation on Parallel Machines, pages 203-212. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. URL: https://doi.org/10.1007/11671541_7.
  15. Stefano Leonardi and Danny Raz. Approximating total flow time on parallel machines. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 110-119, New York, NY, USA, 1997. ACM. URL: https://doi.org/10.1145/258533.258562.
  16. Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. arXiv, 2022. URL: https://doi.org/10.48550/arXiv.2202.10199.
  17. Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 3302-3311, 2018. URL: http://proceedings.mlr.press/v80/lykouris18a.html.
  18. Andres Muñoz Medina and Sergei Vassilvitskii. Revenue optimization with approximate bid predictions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 1858-1866, 2017. URL: http://papers.nips.cc/paper/6782-revenue-optimization-with-approximate-bid-predictions.
  19. Michael Mitzenmacher. Scheduling with Predictions and the Price of Misprediction. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.14.
  20. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint, 2020. URL: https://doi.org/10.48550/arXiv.2006.09123.
  21. Rajeev Motwani, Steven Phillips, and Eric Torng. Nonclairvoyant scheduling. Theoretical computer science, 130(1):17-47, 1994. Google Scholar
  22. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661-9670, 2018. Google Scholar
  23. Wayne E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59-66, 1956. URL: https://doi.org/10.1002/nav.3800030106.
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 About DROPS Imprint Privacy Contact