IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v103y2023i1d10.1007_s11134-022-09849-5.html
   My bibliography  Save this article

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

Author

Listed:
  • William A. Massey

    (Princeton University)

  • Emmanuel Ekwedike

    (Peraton Labs)

  • Robert C. Hampshire

    (University of Michigan)

  • Jamol J. Pender

    (Cornell University)

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.

Suggested Citation

  • William A. Massey & Emmanuel Ekwedike & Robert C. Hampshire & Jamol J. Pender, 2023. "A transient symmetry analysis for the M/M/1/k queue," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 1-43, February.
    • Handle: RePEc:spr:queues:v:103:y:2023:i:1:d:10.1007_s11134-022-09849-5
    DOI: 10.1007/s11134-022-09849-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-022-09849-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-022-09849-5?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Faghih-Imani, Ahmadreza & Hampshire, Robert & Marla, Lavanya & Eluru, Naveen, 2017. "An empirical analysis of bike sharing usage and rebalancing: Evidence from Barcelona and Seville," Transportation Research Part A: Policy and Practice, Elsevier, vol. 97(C), pages 177-191.
    2. Tal Raviv & Ofer Kolka, 2013. "Optimal inventory management of a bike-sharing station," IISE Transactions, Taylor & Francis Journals, vol. 45(10), pages 1077-1093.
    3. William J. Gordon & Gordon F. Newell, 1967. "Cyclic Queuing Systems with Restricted Length Queues," Operations Research, INFORMS, vol. 15(2), pages 266-277, April.
    4. Legros, Benjamin, 2019. "Dynamic repositioning strategy in a bike-sharing system; how to prioritize and how to rebalance a bike station," European Journal of Operational Research, Elsevier, vol. 272(2), pages 740-753.
    5. Christine Fricker & Nicolas Gast, 2016. "Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(3), pages 261-291, August.
    6. William A. Massey, 1987. "Stochastic Orderings for Markov Processes on Partially Ordered Spaces," Mathematics of Operations Research, INFORMS, vol. 12(2), pages 350-367, May.
    7. Bacem Samet & Florent Couffin & Marc Zolghadri & Maher Barkallah & Mohamed Haddar, 2018. "Performance Analysis and Improvement of the Bike Sharing System Using Closed Queuing Networks with Blocking Mechanism," Sustainability, MDPI, vol. 10(12), pages 1-26, December.
    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. Yi Yao & Yifang Zhang & Lixin Tian & Nianxing Zhou & Zhilin Li & Minggang Wang, 2019. "Analysis of Network Structure of Urban Bike-Sharing System: A Case Study Based on Real-Time Data of a Public Bicycle System," Sustainability, MDPI, vol. 11(19), pages 1-17, September.
    2. Yongji Jia & Wang Zeng & Yanting Xing & Dong Yang & Jia Li, 2020. "The Bike-Sharing Rebalancing Problem Considering Multi-Energy Mixed Fleets and Traffic Restrictions," Sustainability, MDPI, vol. 13(1), pages 1-15, December.
    3. Rayane El Sibai & Khalil Challita & Jacques Bou Abdo & Jacques Demerjian, 2021. "A New User-Based Incentive Strategy for Improving Bike Sharing Systems’ Performance," Sustainability, MDPI, vol. 13(5), pages 1-18, March.
    4. Negahban, Ashkan, 2019. "Simulation-based estimation of the real demand in bike-sharing systems in the presence of censoring," European Journal of Operational Research, Elsevier, vol. 277(1), pages 317-332.
    5. Jan Brinkmann & Marlin W. Ulmer & Dirk C. Mattfeld, 2020. "The multi-vehicle stochastic-dynamic inventory routing problem for bike sharing systems," Business Research, Springer;German Academic Association for Business Research, vol. 13(1), pages 69-92, April.
    6. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
    7. Neumann-Saavedra, Bruno Albert & Mattfeld, Dirk Christian & Hewitt, Mike, 2021. "Assessing the operational impact of tactical planning models for bike-sharing redistribution," Transportation Research Part A: Policy and Practice, Elsevier, vol. 150(C), pages 216-235.
    8. Elżbieta Macioszek & Paulina Świerk & Agata Kurek, 2020. "The Bike-Sharing System as an Element of Enhancing Sustainable Mobility—A Case Study based on a City in Poland," Sustainability, MDPI, vol. 12(8), pages 1-29, April.
    9. Kumar Dey, Bibhas & Anowar, Sabreena & Eluru, Naveen, 2021. "A framework for estimating bikeshare origin destination flows using a multiple discrete continuous system," Transportation Research Part A: Policy and Practice, Elsevier, vol. 144(C), pages 119-133.
    10. J. Christopher Westland & Jian Mou & Dafei Yin, 2018. "Prediction of Shared Bicycle Demand with Wavelet Thresholding," Papers 1802.02683, arXiv.org.
    11. Song, Jie & Zhang, Liye & Qin, Zheng & Ramli, Muhamad Azfar, 2021. "Where are public bikes? The decline of dockless bike-sharing supply in Singapore and its resulting impact on ridership activities," Transportation Research Part A: Policy and Practice, Elsevier, vol. 146(C), pages 72-90.
    12. Repoux, Martin & Kaspi, Mor & Boyacı, Burak & Geroliminis, Nikolas, 2019. "Dynamic prediction-based relocation policies in one-way station-based carsharing systems with complete journey reservations," Transportation Research Part B: Methodological, Elsevier, vol. 130(C), pages 82-104.
    13. Gu, Wei & Yu, Xiaoru & Zhang, Shichen & Yan, Xiangbin & Wang, Chen, 2023. "To outsource or not: Bike-share rebalancing strategies under the service quality deviation of a third party," European Journal of Operational Research, Elsevier, vol. 310(2), pages 847-859.
    14. Huang, Di & Chen, Xinyuan & Liu, Zhiyuan & Lyu, Cheng & Wang, Shuaian & Chen, Xuewu, 2020. "A static bike repositioning model in a hub-and-spoke network framework," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    15. Wang, Yi-Jia & Kuo, Yong-Hong & Huang, George Q. & Gu, Weihua & Hu, Yaohua, 2022. "Dynamic demand-driven bike station clustering," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 160(C).
    16. Lv, Chang & Zhang, Chaoyong & Lian, Kunlei & Ren, Yaping & Meng, Leilei, 2020. "A hybrid algorithm for the static bike-sharing re-positioning problem based on an effective clustering strategy," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 1-21.
    17. Imen Haj Salah & Vasu Dev Mukku & Malte Kania & Tom Assmann & Hartmut Zadek, 2022. "Implications of the Relocation Type and Frequency for Shared Autonomous Bike Service: Comparison between the Inner and Complete City Scenarios for Magdeburg as a Case Study," Sustainability, MDPI, vol. 14(10), pages 1-18, May.
    18. Çelebi, Dilay & Yörüsün, Aslı & Işık, Hanife, 2018. "Bicycle sharing system design with capacity allocations," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 86-98.
    19. Liang Gao & Wei Xu & Yifeng Duan, 2019. "Dynamic Scheduling Based on Predicted Inventory Variation Rate for Public Bicycle System," Sustainability, MDPI, vol. 11(7), pages 1-11, March.
    20. Quan-Lin Li & Rui-Na Fan, 2022. "A mean-field matrix-analytic method for bike sharing systems under Markovian environment," Annals of Operations Research, Springer, vol. 309(2), pages 517-551, February.

    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:spr:queues:v:103:y:2023:i:1:d:10.1007_s11134-022-09849-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.