Document Open Access Logo

Restricted Adaptivity in Stochastic Scheduling

Authors Guillaume Sagnol , Daniel Schmidt genannt Waldschmidt

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.79.pdf
  • Filesize: 0.9 MB
  • 14 pages

Document Identifiers

Author Details

Guillaume Sagnol
  • Institut für Mathematik, TU Berlin, Germany
Daniel Schmidt genannt Waldschmidt
  • Institut für Mathematik, TU Berlin, Germany

Funding

Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt were funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

Acknowledgements

We thank Thibault Juillard for helpful discussions on the topic of this paper. We also thank the anonymous referees for helpful comments.

Cite AsGet BibTex

Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.79

Abstract

We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω((log m)/(log log m)). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an 𝒪(log log m)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • stochastic scheduling
  • makespan minimzation
  • approximation algorithm
  • fixed assignment policy
  • non-anticipatory policy

Metrics

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

Related Versions

References

  1. Gagan Aggarwal, Rajeev Motwani, and An Zhu. The load rebalancing problem. Journal of Algorithms, 60(1):42-59, 2006. Google Scholar
  2. Susanne Albers and Matthias Hellwig. On the value of job migration in online makespan minimization. Algorithmica, 79(2):598-623, 2017. Google Scholar
  3. Noga Alon, Yossi Azar, Gerhard J. Woeginger, and Tal Yadid. Approximation schemes for scheduling on parallel machines. Journal of Scheduling, 1(1):55-66, 1998. Google Scholar
  4. B.P. Berg and B.T. Denton. Fast approximation methods for online scheduling of outpatient procedure centers. INFORMS Journal on Computing, 29(4):631-644, 2017. Google Scholar
  5. Lin Chen, Klaus Jansen, and Guochuan Zhang. On the optimality of approximation schemes for the classical scheduling problem. In ACM-SIAM Symposium on Discrete Algorithms, pages 657-668, 2013. Google Scholar
  6. Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey. An efficient PTAS for stochastic load balancing with poisson jobs. In 47th International Colloquium on Automata, Languages, and Programming, volume 168 of LIPIcs, pages 37:1-37:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  7. Brian T. Denton, Andrew J. Miller, Hari J. Balasubramanian, and Todd R. Huschka. Optimal allocation of surgery blocks to operating rooms under uncertainty. Operations Research, 58(4-1):802-816, 2010. Google Scholar
  8. Matthias Englert, Deniz Ozmen, and Matthias Westermann. The power of reordering for online minimum makespan scheduling. SIAM Journal on Computing, 43(3):1220-1237, 2014. Google Scholar
  9. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness, 1979. Google Scholar
  10. Ashish Goel and Piotr Indyk. Stochastic load balancing and related problems. In 40th Annual Symposium on Foundations of Computer Science, pages 579-586. IEEE, 1999. Google Scholar
  11. Ronald L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9):1563-1581, 1966. Google Scholar
  12. Ronald L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  13. Ronald L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of Discrete Mathematics, volume 5, pages 287-326. Elsevier, 1979. Google Scholar
  14. Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. Stochastic load balancing on unrelated machines. Mathematics of Operations Research, 46(1):115-133, 2021. Google Scholar
  15. Varun Gupta, Benjamin Moseley, Marc Uetz, and Qiaomin Xie. Greed works—online algorithms for unrelated machine stochastic scheduling. Mathematics of Operations Research, 45(2):497-516, 2020. Google Scholar
  16. Willy Herroelen and Roel Leus. Robust and reactive project scheduling: a review and classification of procedures. International Journal of Production Research, 42(8):1599-1620, 2004. Google Scholar
  17. Dorit S. Hochbaum. Various notions of approximations: Good, better, best and more. Approximation algorithms for NP-hard problems, 1997. Google Scholar
  18. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM, 34(1):144-162, 1987. Google Scholar
  19. Dorit S. Hochbaum and David B. Shmoys. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM Journal on Computing, 17(3):539-551, 1988. Google Scholar
  20. David Isern, David Sánchez, and Antonio Moreno. Agents applied in health care: A review. International journal of medical informatics, 79(3):145-166, 2010. Google Scholar
  21. Klaus Jansen. An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics, 24(2):457-485, 2010. Google Scholar
  22. Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the gap for makespan scheduling via sparsification techniques. Mathematics of Operations Research, 45(4):1371-1392, 2020. Google Scholar
  23. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Allocating bandwidth for bursty connections. SIAM Journal on Computing, 30(1):191-217, 2000. Google Scholar
  24. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, 46(1):259-271, 1990. Google Scholar
  25. Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and algorithms for stochastic online scheduling. Mathematics of Operations Research, 31(3):513-525, 2006. Google Scholar
  26. Rolf H. Möhring, Franz Josef Radermacher, and Gideon Weiss. Stochastic scheduling problems I—general strategies. Zeitschrift für Operations Research, 28(7):193-260, 1984. Google Scholar
  27. Rolf H. Möhring, Andreas S. Schulz, and Marc Uetz. Approximation in stochastic scheduling: the power of lp-based priority policies. Journal of the ACM, 46(6):924-942, 1999. Google Scholar
  28. Marco Molinaro. Stochastic lp load balancing and moment problems via the l-function method. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 343-354. SIAM, 2019. Google Scholar
  29. Guillaume Sagnol, Christoph Barner, Ralf Borndörfer, Mickaël Grima, Mathees Seeling, Claudia Spies, and Klaus Wernecke. Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations. European Journal of Operational Research, 271(2):420-435, 2018. Google Scholar
  30. Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt. Restricted adaptivity in stochastic scheduling, 2021. URL: http://arxiv.org/abs/2106.15393.
  31. Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt, and Alexander Tesch. The price of fixed assignments in stochastic extensible bin packing. In International Workshop on Approximation and Online Algorithms, pages 327-347. Springer, 2018. Google Scholar
  32. Sartaj K. Sahni. Algorithms for scheduling independent tasks. Journal of the ACM, 23(1):116-127, 1976. Google Scholar
  33. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Google Scholar
  34. Andreas S. Schulz. Stochastic online scheduling revisited. In International Conference on Combinatorial Optimization and Applications, pages 448-457. Springer, 2008. Google Scholar
  35. Martin Skutella, Maxim Sviridenko, and Marc Uetz. Unrelated machine scheduling with stochastic processing times. Mathematics of Operations Research, 41(3):851-864, 2016. Google Scholar
  36. Guanlian Xiao, Willem van Jaarsveld, Ming Dong, and Joris van de Klundert. Models, algorithms and performance analysis for adaptive operating room scheduling. International Journal of Production Research, 56(4):1389-1413, 2018. 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