IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i3p766-786.html
   My bibliography  Save this article

Supervised ML for Solving the GI / GI /1 Queue

Author

Listed:
  • Opher Baron

    (Rotman School Of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

  • Dmitry Krass

    (Rotman School Of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

  • Arik Senderovich

    (School of Information Technologies (ITEC), York University, Toronto, Ontario M3J 1P3, Canada)

  • Eliran Sherzer

    (Rotman School Of Management, University of Toronto, Toronto, Ontario M5S 3E6, Canada)

Abstract

We apply supervised learning to a general problem in queueing theory: using a neural net , we develop a fast and accurate predictor of the stationary system-length distribution of a GI / GI /1 queue—a fundamental queueing model for which no analytical solutions are available. To this end, we must overcome three main challenges: (i) generating a large library of training instances that cover a wide range of arbitrary interarrival and service time distributions, (ii) labeling the training instances, and (iii) providing continuous arrival and service distributions as inputs to the neural net. To overcome (i), we develop an algorithm to sample phase-type interarrival and service time distributions with complex transition structures. We demonstrate that our distribution-generating algorithm indeed covers a wide range of possible positive-valued distributions. For (ii), we label our training instances via quasi-birth-and-death(QBD) that was used to approximate PH / PH /1 (with phase-type arrival and service process) as labels for the training data. For (iii), we find that using only the first five moments of both the interarrival and service times distribution as inputs is sufficient to train the neural net. Our empirical results show that our neural model can estimate the stationary behavior of the GI / GI /1—far exceeding other available methods in terms of both accuracy and runtimes.

Suggested Citation

  • Opher Baron & Dmitry Krass & Arik Senderovich & Eliran Sherzer, 2024. "Supervised ML for Solving the GI / GI /1 Queue," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 766-786, May.
  • Handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:766-786
    DOI: 10.1287/ijoc.2022.0263
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0263
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2022.0263?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Marc Hallin & Gilles Mordant & Johan Segers, 2020. "Multivariate Goodness-of-Fit Tests Based on Wasserstein Distance," Working Papers ECARES 2020-06, ULB -- Universite Libre de Bruxelles.
    2. Baric{s} Ata & Shiri Shneorson, 2006. "Dynamic Control of an M/M/1 Service System with Adjustable Arrival and Service Rates," Management Science, INFORMS, vol. 52(11), pages 1778-1791, November.
    3. Ward Whitt & Wei You, 2018. "Using Robust Queueing to Expose the Impact of Dependence in Single-Server Queues," Operations Research, INFORMS, vol. 66(1), pages 184-199, January.
    4. Rob Mei & Sandjai Bhulai, 2022. "A data-driven approach to deriving closed-form approximations for queueing problems using genetic algorithms," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 549-551, April.
    5. Jennifer M. George & J. Michael Harrison, 2001. "Dynamic Control of a Queue with Adjustable Service Rate," Operations Research, INFORMS, vol. 49(5), pages 720-731, October.
    6. Amir Rastpour & Armann Ingolfsson & Burhaneddin Sandıkçı, 2022. "Algorithms for Queueing Systems with Reneging and Priorities Modeled as Quasi-Birth-Death Processes," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1693-1710, May.
    7. Seelen, L. P., 1986. "An algorithm for Ph/Ph/c queues," European Journal of Operational Research, Elsevier, vol. 23(1), pages 118-127, January.
    8. Dmitry Efrosinin & Natalia Stepanova, 2021. "Estimation of the Optimal Threshold Policy in a Queue with Heterogeneous Servers Using a Heuristic Solution and Artificial Neural Networks," Mathematics, MDPI, vol. 9(11), pages 1-14, May.
    9. Barış Tan & Siamak Khayyati, 2022. "Supervised learning-based approximation method for single-server open queueing networks with correlated interarrival and service times," International Journal of Production Research, Taylor & Francis Journals, vol. 60(22), pages 6822-6847, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shone, Rob & Glazebrook, Kevin & Zografos, Konstantinos G., 2019. "Resource allocation in congested queueing systems with time-varying demand: An application to airport operations," European Journal of Operational Research, Elsevier, vol. 276(2), pages 566-581.
    2. Sami Najafi-Asadolahi & Kristin Fridgeirsdottir, 2014. "Cost-per-Click Pricing for Display Advertising," Manufacturing & Service Operations Management, INFORMS, vol. 16(4), pages 482-497, October.
    3. Carri W. Chan & Vivek F. Farias & Gabriel J. Escobar, 2017. "The Impact of Delays on Service Times in the Intensive Care Unit," Management Science, INFORMS, vol. 63(7), pages 2049-2072, July.
    4. Dimitrakopoulos, Y. & Burnetas, A.N., 2016. "Customer equilibrium and optimal strategies in an M/M/1 queue with dynamic service control," European Journal of Operational Research, Elsevier, vol. 252(2), pages 477-486.
    5. Legros, Benjamin, 2022. "The principal-agent problem for service rate event-dependency," European Journal of Operational Research, Elsevier, vol. 297(3), pages 949-963.
    6. Wallace J. Hopp & Seyed M. R. Iravani & Gigi Y. Yuen, 2007. "Operations Systems with Discretionary Task Completion," Management Science, INFORMS, vol. 53(1), pages 61-77, January.
    7. Benjamin Legros, 2022. "The principal-agent problem for service rate event-dependency," Post-Print hal-03605421, HAL.
    8. Xiaojun Liang & Yinghui Tang, 2019. "The improvement upon the reliability of the k-out-of-n:F system with the repair rates differentiation policy," Operational Research, Springer, vol. 19(2), pages 479-500, June.
    9. Barιş Ata & Deishin Lee & Erkut Sönmez, 2019. "Dynamic Volunteer Staffing in Multicrop Gleaning Operations," Operations Research, INFORMS, vol. 67(2), pages 295-314, March.
    10. Xia, Li, 2014. "Service rate control of closed Jackson networks from game theoretic perspective," European Journal of Operational Research, Elsevier, vol. 237(2), pages 546-554.
    11. Ying Xu & Alan Scheller-Wolf & Katia Sycara, 2015. "The Benefit of Introducing Variability in Single-Server Queues with Application to Quality-Based Service Domains," Operations Research, INFORMS, vol. 63(1), pages 233-246, February.
    12. René Caldentey & Lawrence M. Wein, 2006. "Revenue Management of a Make-to-Stock Queue," Operations Research, INFORMS, vol. 54(5), pages 859-875, October.
    13. Jinting Wang & Zhongbin Wang & Yunan Liu, 2020. "Reducing Delay in Retrial Queues by Simultaneously Differentiating Service and Retrial Rates," Operations Research, INFORMS, vol. 68(6), pages 1648-1667, November.
    14. Ghosh, Arka P. & Weerasinghe, Ananda P., 2010. "Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic," Stochastic Processes and their Applications, Elsevier, vol. 120(11), pages 2103-2141, November.
    15. Chen-An Lin & Kevin Shang & Peng Sun, 2023. "Wait Time–Based Pricing for Queues with Customer-Chosen Service Times," Management Science, INFORMS, vol. 69(4), pages 2127-2146, April.
    16. Pei, Zhi & Dai, Xu & Yuan, Yilun & Du, Rui & Liu, Changchun, 2021. "Managing price and fleet size for courier service with shared drones," Omega, Elsevier, vol. 104(C).
    17. Solveig Flaig & Gero Junike, 2022. "Scenario Generation for Market Risk Models Using Generative Neural Networks," Risks, MDPI, vol. 10(11), pages 1-28, October.
    18. Ward Whitt, 1999. "Partitioning Customers into Service Groups," Management Science, INFORMS, vol. 45(11), pages 1579-1592, November.
    19. Ward Whitt & Wei You, 2022. "New decomposition approximations for queueing networks," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 365-367, April.
    20. Delasay, Mohammad & Ingolfsson, Armann & Kolfal, Bora & Schultz, Kenneth, 2019. "Load effect on service times," European Journal of Operational Research, Elsevier, vol. 279(3), pages 673-686.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:766-786. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.