Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A transient symmetry analysis for the M/M/1/k queue

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

We develop new techniques involving group symmetries and complex analysis to obtain exact solutions for the transition probabilities of the M/M/1/k queueing process. These methods are based on the underlying Markovian structure of these random processes and do not involve any generating functions, Laplace transforms, or advanced special functions. Our techniques exploit the intrinsic group symmetries for both the state spaces and the matrix generators of the Markov processes related to the M/M/1/k queue. These results complement and extend the previous transient solutions given by Takács (Introduction to the theory of queues. University texts in the mathematical sciences, Oxford University Press, New York, 1962). Much of the inspiration for this work comes from viewing this queueing process as a fundamental Markovian model for the dynamics of a bike sharing station. The exact transient analysis for a related stopped version of this process can be used to address fundamental decision-making issues for managing bike-sharing services.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

Notes

  1. Generalization of these functions was introduced in Baccelli et al. [4] where the roles of \(\delta \) and \(\epsilon \) were reversed from how they are used here.

  2. The generalizations of these functions in Baccelli et al. [4] reverse the roles of \(\delta \) and \(\epsilon \).

References

  1. Altman, E., Jean-Marie, A.: The loss process of messages in an \(M/M/1/k\) queue. In: Proceedings of INFOCOM’94 Conference on Computer Communications, pp. 1191–1198. IEEE (1994)

  2. Baccelli, F., Massey, W.A.: On the busy period of certain classes of queueing networks. In: Computer Performance and Reliability (1987)

  3. Baccelli, F., Massey, W.A.: A sample path analysis of the m/m/1 queue. J. Appl. Probab. 26(2), 418–422 (1989)

    Article  Google Scholar 

  4. Baccelli, F., Massey, W.A., Wright, P.E.: Determining the exit time distribution for a closed cyclic network. Theor Comput Sci 125(1), 149–165 (1994)

    Article  Google Scholar 

  5. Biondi, E., Boldrini, C., Bruno, R.: The impact of regulated electric fleets on the power grid: the car sharing case. In: 2016 IEEE 2nd International Forum on Research and Technologies for Society and Industry Leveraging a Better Tomorrow (RTSI), pp. 1–6. IEEE (2016)

  6. Calafiore, G.C., Portigliotti, F., Rizzo, A.: A network model for an urban bike sharing system. IFAC-PapersOnLine 50(1), 15633–15638 (2017)

    Article  Google Scholar 

  7. Chemla, D., Meunier, F., Calvo, R.W.: Bike sharing systems: solving the static rebalancing problem. Discrete Optim. 10(2), 120–146 (2013)

    Article  Google Scholar 

  8. Chen, M., Shen, W., Tang, P., Zuo, S.: Optimal vehicle dispatching for ride-sharing platforms via dynamic pricing. In: Companion Proceedings of the the Web Conference 2018, pp. 51–52 (2018)

  9. Chung, H., Freund, D., Shmoys, D.B.: Bike angels: an analysis of citi bike’s incentive program. In: Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, pp. 1–9 (2018)

  10. Cohen, J.W.: The Single Server Queue. Elsevier, Amsterdam (2012)

    Google Scholar 

  11. Cohen, J.W.: On the busy periods for the M/G/1 queue with finite and with infinite waiting room. J. Appl. Probab. 8, 821–827 (1971)

    Article  Google Scholar 

  12. Daw, A., Pender, J.: An ephemerally self-exciting point process. Adv. Appl. Probab. 54(2), 340–403 (2022). https://doi.org/10.1017/apr.2021.35

  13. Daw, A., Pender, J.: Queues driven by hawkes processes. Stoch. Syst. 8(3), 192–229 (2018)

    Article  Google Scholar 

  14. Dummit, D.S., Foote, R.M.: Abstract Algebra, vol. 1999. Prentice Hall, Englewood Cliffs (1991)

    Google Scholar 

  15. Ekwedike, E.C.: Optimal decision making via stochastic modeling and machine learning. Ph.D. thesis, Princeton University (2020)

  16. Faghih-Imani, A., Hampshire, R., Marla, L., Eluru, N.: An empirical analysis of bike sharing usage and rebalancing: evidence from Barcelona and Seville. Transp. Res. Part A Policy Pract. 97, 177–191 (2017)

    Article  Google Scholar 

  17. Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 2. Wiley, Hoboken (2008)

    Google Scholar 

  18. Fricker, C., Gast, N.: Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity. Euro J. Transp. Logist. 5(3), 261–291 (2016)

    Article  Google Scholar 

  19. Fricker, C., Gast, N., Mohamed, H.: Mean field analysis for inhomogeneous bike sharing systems. In: Discrete Mathematics and Theoretical Computer Science (2012)

  20. Gordon, W.J., Newell, G.F.: Cyclic queuing systems with restricted length queues. Oper. Res. 15(2), 266–277 (1967)

    Article  Google Scholar 

  21. Gouweleeuw, F.N.: The loss probability in an overloaded queue using the dual queue. Oper. Res. Lett. 21(2), 101–106 (1997)

    Article  Google Scholar 

  22. Grier, N., Massey, W.A., McKoy, T., Whitt, W.: The time-dependent erlang loss model with retrials. Telecommun. Syst. 7(1), 253–265 (1997)

    Article  Google Scholar 

  23. Hampshire, R.C., Marla, L.: An analysis of bike sharing usage: explaining trip generation and attraction from observed demand. In: 91st Annual Meeting of the Transportation Research Board, Washington, DC, pp. 12–2099 (2012)

  24. Hautphenne, S., Haviv, M.: The bias optimal \(k\) in the \(M/M/1/k\) queue: an application of the deviation matrix. Probab. Eng. Inf. Sci. 30(1), 61 (2016)

    Article  Google Scholar 

  25. Huang, J., Sun, H., Li, H., Huang, L., Li, A., Wang, X.: Central station-based demand prediction for determining target inventory in a bike-sharing system. Comput. J. 65, 573–588 (2020)

    Article  Google Scholar 

  26. Karlin, S., McGregor, J.: The classification of birth and death processes. Trans. Am. Math. Soc. 86(2), 366–400 (1957)

    Article  Google Scholar 

  27. Kelly, F.P.: Reversibility and Stochastic Networks. Cambridge University Press, Cambridge (2011)

    Google Scholar 

  28. Koops, D.T., Saxena, M., Boxma, O.J., Mandjes, M.: Infinite-server queues with Hawkes input. J. Appl. Probab. 55(3), 920–943 (2018)

    Article  Google Scholar 

  29. Kosek-Szott, K.: Throughput, delay, and frame loss probability analysis of IEEE 802.11 DCF with \(M/M/1/k\) queues. In: 2013 IEEE 24th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), pp. 2234–2238. IEEE (2013)

  30. Kumar, R., Sharma, S.K.: M/m/1/n queuing system with retention of reneged customers. Pak. J. Stat. Oper. Res. 8, 859–866 (2012)

    Article  Google Scholar 

  31. Legros, B.: Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station. Eur. J. Oper. Res. 272(2), 740–753 (2019)

    Article  Google Scholar 

  32. Li, Q.-L., Chen, C., Fan, R.-N., Xu, L., Ma, J.-Y.: Queueing analysis of a large-scale bike sharing system through mean-field theory (2016). arXiv preprint arXiv:1603.09560

  33. Li, Q.-L., Fan, R.-N., Qian, Z.-Y.: A nonlinear solution to closed queueing networks for bike sharing systems with Markovian arrival processes and under an irreducible path graph. In: International Conference on Queueing Theory and Network Applications, pp. 118–140. Springer (2017)

  34. Massey, W.A.: Calculating exit times for series Jackson networks. J. Appl. Probab. 24, 226–234 (1987)

    Article  Google Scholar 

  35. Massey, W.A.: Stochastic orderings for Markov processes on partially ordered spaces. Math. Oper. Res. 12(2), 350–367 (1987)

    Article  Google Scholar 

  36. Mathers, J.: The barber queue. Math. Teacher 69(8), 680–684 (1976)

    Article  Google Scholar 

  37. Nair, R., Miller-Hooks, E., Hampshire, R.C., Bušić, A.: Large-scale vehicle sharing systems: analysis of Vélib’. Int. J. Sustain. Transp. 7(1), 85–106 (2013)

    Article  Google Scholar 

  38. O’Mahony, E., Shmoys, D.: Data analysis and optimization for (Citi) bike sharing. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29 (2015)

  39. Pan, L., Cai, Q., Fang, Z., Tang, P., Huang, L.: A deep reinforcement learning framework for rebalancing dockless bike sharing systems. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 1393–1400 (2019)

  40. Parthasarathy, P.R.: A transient solution to an m/m/1 queue: a simple approach. Adv. Appl. Probab. 19(4), 997–998 (1987)

    Article  Google Scholar 

  41. Pender, J.: Gram charlier expansion for time varying multiserver queues with abandonment. SIAM J. Appl. Math. 74(4), 1238–1265 (2014)

    Article  Google Scholar 

  42. Pender, J.: Nonstationary loss queues via cumulant moment approximations. Probab. Eng. Inf. Sci. 29(1), 27 (2015)

    Article  Google Scholar 

  43. Pender, J., Tao, S., Wikum, A.: A stochastic model for electric scooter systems. Available at SSRN 3582320 (2020)

  44. Raviv, T., Kolka, O.: Optimal inventory management of a bike-sharing station. Iie Trans. 45(10), 1077–1093 (2013)

    Article  Google Scholar 

  45. Righter, R.: A note on losses in M/GI/1/n queues. J. Appl. Probab. 36, 1240–1243 (1999)

    Article  Google Scholar 

  46. Rosenlund, S.I.: On the length and number of served customers of the busy period of a generalised m/g/1 queue with finite waiting room. Adv. Appl. Probab. 5, 379–389 (1973)

    Article  Google Scholar 

  47. Rubino, G.: Transient analysis of Markovian queueing systems: a survey with focus on closed forms and uniformization. In: Queueing Theory 2: Advanced Trends, pp. 269–307 (2021)

  48. Samet, B., Couffin, F., Barkallah, M., Zolghadri, M., Haddar, M.: Performance evaluation using closed queueing network in bike sharing systems. In: International Conference on Acoustics and Vibration, ICAV2016 (2016)

  49. Samet, B., Couffin, F., Zolghadri, M., Barkallah, M., Haddar, M.: Performance analysis and improvement of the bike sharing system using closed queuing networks with blocking mechanism. Sustainability 10(12), 4663 (2018)

    Article  Google Scholar 

  50. Schuijbroek, J., Hampshire, R.C., Van Hoeve, W.-J.: Inventory rebalancing and vehicle routing in bike sharing systems. Eur. J. Oper. Res. 257(3), 992–1004 (2017)

    Article  Google Scholar 

  51. Sharma, O.P., Tarabia, A.M.K.: A simple transient analysis of an m/m/1/n queue. Sankhyā Indian J. Stat. Ser. A 273–281 (2000)

  52. Skellam, J.G.: The frequency distribution of the difference between two Poisson variates belonging to different populations. J. R. Stat. Soc. Ser. A (Gen.) 109(Pt 3), 296 (1946)

    Article  Google Scholar 

  53. Takács, L.: Introduction to the Theory of Queues. University Texts in the Mathematical Sciences. Oxford University Press, New York (1962)

    Google Scholar 

  54. Tao, S.: Limit theorems in queueing networks with applications to shared mobility and healthcare. Ph.D. thesis, Cornell University (2020)

  55. Tao, S., Pender, J.: The impact of smartphone apps on bike sharing systems. Available at SSRN 3582275 (2020)

  56. Tao, S., Pender, J.: A stochastic analysis of bike-sharing systems. Probab. Eng. Inf. Sci. (2020). https://doi.org/10.1017/S0269964820000297

    Article  Google Scholar 

  57. Upton, R.A., Tripathi, S.K.: An approximate transient analysis of the M(t)/M/1 queue. Perform. Eval. 2(2), 118–132 (1982)

    Article  Google Scholar 

  58. van Doorn, E.A.: Shell polynomials and dual birth-death processes. In: Symmetry, Integrability and Geometry: Methods and Applications (2016). ISSN 1815-0659

  59. Vogel, P., Greiser, T., Mattfeld, D.C.: Understanding bike-sharing systems using data mining: exploring activity patterns. Procedia Soc. Behav. Sci. 20, 514–523 (2011)

    Article  Google Scholar 

  60. Waserhole, A., Jost, V., Brauner, N.: Pricing techniques for self regulation in vehicle sharing systems. Electron. Notes Discrete Math. 41, 149–156 (2013)

    Article  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the Institute for Advanced Study for their hospitality and funding where this work was conceived and completed. This research began with our collective involvement in the IAS Summer Collaborators Program in July 2019 and concluded with the visit of the first author to IAS as a member of the school of mathematics from September 2020 to July 2021 during his sabbatical from Princeton University. Much of this work also served as a basis for a major part of the PhD dissertation of the second author, see Ekwedike [15]. Finally, the authors would also like to thank Alfred Nöel for his feedback and suggestions at the Institute for Advanced Study.

Author information

Authors and Affiliations

  1. Department of Operations Research and Financial Engineering, Princeton University, Princeton, USA

    William A. Massey

  2. Peraton Labs, Basking Ridge, USA

    Emmanuel Ekwedike

  3. Gerald R. Ford School of Public Policy, University of Michigan, Ann Arbor, USA

    Robert C. Hampshire

  4. School of Operations Research and Information Engineering, Cornell University, Ithaca, USA

    Jamol J. Pender

Authors
  1. William A. Massey
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Emmanuel Ekwedike
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert C. Hampshire
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jamol J. Pender
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jamol J. Pender.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Massey, W.A., Ekwedike, E., Hampshire, R.C. et al. A transient symmetry analysis for the M/M/1/k queue. Queueing Syst 103, 1–43 (2023). https://doi.org/10.1007/s11134-022-09849-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-022-09849-5

Keywords

Search

Navigation