IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v266y2018i2p609-621.html
   My bibliography  Save this article

Modelling deadlock in open restricted queueing networks

Author

Listed:
  • Palmer, Geraint I.
  • Harper, Paul R.
  • Knight, Vincent A.

Abstract

Open restricted queueing networks give rise to the phenomenon of deadlock, whereby some customers may be unable to ever leave a server due to mutual blocking. This paper explores deadlock in queueing networks with limited queueing capacity, presents a method of detecting deadlock in discrete event simulations, and builds Markov chain models of these deadlocking networks. The three networks for which Markov models are given include single and multi-server networks for one and two node systems. The expected times to deadlock of these models are compared to results obtained using a simulation of the stochastic process, together with the developed deadlock detection method. This paper aims to be of value to simulation modellers of queues.

Suggested Citation

  • Palmer, Geraint I. & Harper, Paul R. & Knight, Vincent A., 2018. "Modelling deadlock in open restricted queueing networks," European Journal of Operational Research, Elsevier, vol. 266(2), pages 609-621.
    • Handle: RePEc:eee:ejores:v:266:y:2018:i:2:p:609-621
    DOI: 10.1016/j.ejor.2017.10.039
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717309529
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.10.039?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. Florian, Michael & Mahut, Michael & Tremblay, Nicolas, 2008. "Application of a simulation-based dynamic traffic assignment model," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1381-1392, September.
    2. B. Avi-Itzhak & M. Yadin, 1965. "A Sequence of Two Servers with No Intermediate Queue," Management Science, INFORMS, vol. 11(5), pages 553-564, March.
    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. Yves Dallery & Yannick Frein, 1993. "On Decomposition Methods for Tandem Queueing Networks with Blocking," Operations Research, INFORMS, vol. 41(2), pages 386-399, April.
    5. Gordon C. Hunt, 1956. "Sequential Arrays of Waiting Lines," Operations Research, INFORMS, vol. 4(6), pages 674-683, December.
    6. Korporaal, R. & Ridder, A.A.N. & Kloprogge, P. & Dekker, R., 1999. "Capacity planning of prisons in the Netherlands," Econometric Institute Research Papers EI 9909-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. R Korporaal & A Ridder & P Kloprogge & R Dekker, 2000. "An analytic model for capacity planning of prisons in the Netherlands," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(11), pages 1228-1237, November.
    8. Osorio, Carolina & Bierlaire, Michel, 2009. "An analytic finite capacity queueing network model capturing the propagation of congestion and blocking," European Journal of Operational Research, Elsevier, vol. 196(3), pages 996-1007, August.
    9. Schmidt, Linda C. & Jackman, John, 2000. "Modeling recirculating conveyors with blocking," European Journal of Operational Research, Elsevier, vol. 124(2), pages 422-436, July.
    10. Yutaka Takahashi & Hideo Miyahara & Toshiharu Hasegawa, 1980. "An Approximation Method for Open Restricted Queueing Networks," Operations Research, INFORMS, vol. 28(3-part-i), pages 594-602, June.
    11. Gad Allon & Sarang Deo & Wuqin Lin, 2013. "The Impact of Size and Occupancy of Hospital on the Extent of Ambulance Diversion: Theory and Evidence," Operations Research, INFORMS, vol. 61(3), pages 544-562, June.
    12. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    13. Marchetti, Olivier & Munier-Kordon, Alix, 2009. "A sufficient condition for the liveness of weighted event graphs," European Journal of Operational Research, Elsevier, vol. 197(2), pages 532-540, September.
    14. Bryan L. Deuermeyer & Guy L. Curry & Andrew T. Duchowski & Srilakshmi Venkatesh, 1997. "An Automatic Approach to Deadlock Detection and Resolution in Discrete Simulation Systems," INFORMS Journal on Computing, INFORMS, vol. 9(2), pages 195-205, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Farida F. Galimulina & Naira V. Barsegyan, 2024. "Application of Mass Service Theory to Economic Systems Optimization Problems—A Review," Mathematics, MDPI, vol. 12(3), pages 1-18, January.
    2. Chesoong Kim & Sergey Dudin & Alexander Dudin & Konstantin Samouylov, 2019. "Analysis of a Semi-Open Queuing Network with a State Dependent Marked Markovian Arrival Process, Customers Retrials and Impatience," Mathematics, MDPI, vol. 7(8), pages 1-19, August.

    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. Papadopoulos, H. T. & Heavey, C., 1996. "Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines," European Journal of Operational Research, Elsevier, vol. 92(1), pages 1-27, July.
    2. Saied Samiedaluie & Vedat Verter, 2019. "The impact of specialization of hospitals on patient access to care; a queuing analysis with an application to a neurological hospital," Health Care Management Science, Springer, vol. 22(4), pages 709-726, December.
    3. Osorio, Carolina & Wang, Carter, 2017. "On the analytical approximation of joint aggregate queue-length distributions for traffic networks: A stationary finite capacity Markovian network approach," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 305-339.
    4. Noa Zychlinski & Avishai Mandelbaum & Petar Momčilović, 2018. "Time-varying tandem queues with blocking: modeling, analysis, and operational insights via fluid models with reflection," Queueing Systems: Theory and Applications, Springer, vol. 89(1), pages 15-47, June.
    5. Genji Yamazaki & Hirotaka Sakasegawa, 1975. "Properties of duality in tandem queueing systems," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 27(1), pages 201-212, December.
    6. Korporaal, R. & Ridder, A.A.N. & Kloprogge, P. & Dekker, R., 1999. "Capacity planning of prisons in the Netherlands," Econometric Institute Research Papers EI 9909-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    7. Osorio, Carolina & Bierlaire, Michel, 2009. "An analytic finite capacity queueing network model capturing the propagation of congestion and blocking," European Journal of Operational Research, Elsevier, vol. 196(3), pages 996-1007, August.
    8. Osorio, Carolina & Bierlaire, Michel, 2012. "A tractable analytical model for large-scale congested protein synthesis networks," European Journal of Operational Research, Elsevier, vol. 219(3), pages 588-597.
    9. Tako, Antuela A. & Robinson, Stewart, 2010. "Model development in discrete-event simulation and system dynamics: An empirical study of expert modellers," European Journal of Operational Research, Elsevier, vol. 207(2), pages 784-794, December.
    10. A. Gómez‐Corral, 2004. "Sojourn times in a two‐stage queueing network with blocking," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(8), pages 1068-1089, December.
    11. Noa Zychlinski & Avishai Mandelbaum & Petar Momčilović & Izack Cohen, 2020. "Bed Blocking in Hospitals Due to Scarce Capacity in Geriatric Institutions—Cost Minimization via Fluid Models," Manufacturing & Service Operations Management, INFORMS, vol. 22(2), pages 396-411, March.
    12. Carolina Osorio & Jana Yamani, 2017. "Analytical and Scalable Analysis of Transient Tandem Markovian Finite Capacity Queueing Networks," Transportation Science, INFORMS, vol. 51(3), pages 823-840, August.
    13. J. P. van der Gaast & M. B. M. de Koster & I. J. B. F. Adan, 2018. "Conveyor Merges in Zone Picking Systems: A Tractable and Accurate Approximate Model," Service Science, INFORMS, vol. 52(6), pages 1428-1443, December.
    14. Hirotaka Sakasegawa & Genji Yamazaki, 1977. "Inequalities and an approximation formula for the mean delay time in tandem queueing systems," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 29(1), pages 445-466, December.
    15. Wu, Xiaodan & Li, Juan & Chu, Chao-Hsien, 2019. "Modeling multi-stage healthcare systems with service interactions under blocking for bed allocation," European Journal of Operational Research, Elsevier, vol. 278(3), pages 927-941.
    16. Jelmer P. van der Gaast & René B. M. de Koster & Ivo J. B. F. Adan & Jacques A. C. Resing, 2020. "Capacity Analysis of Sequential Zone Picking Systems," Operations Research, INFORMS, vol. 68(1), pages 161-179, January.
    17. Caroline Lloyd & Jonathan Payne, 2021. "Fewer jobs, better jobs? An international comparative study of robots and ‘routine’ work in the public sector," Industrial Relations Journal, Wiley Blackwell, vol. 52(2), pages 109-124, March.
    18. Fatemeh Nourmohammadi & Mohammadhadi Mansourianfar & Sajjad Shafiei & Ziyuan Gu & Meead Saberi, 2021. "An Open GMNS Dataset of a Dynamic Multi-Modal Transportation Network Model of Melbourne, Australia," Data, MDPI, vol. 6(2), pages 1-9, February.
    19. Eva K. Lee & Siddhartha Maheshwary & Jacquelyn Mason & William Glisson, 2006. "Large-Scale Dispensing for Emergency Response to Bioterrorism and Infectious-Disease Outbreak," Interfaces, INFORMS, vol. 36(6), pages 591-607, December.
    20. Konstantinos S. Boulas & Georgios D. Dounias & Chrissoleon T. Papadopoulos, 2023. "A hybrid evolutionary algorithm approach for estimating the throughput of short reliable approximately balanced production lines," Journal of Intelligent Manufacturing, Springer, vol. 34(2), pages 823-852, 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:eee:ejores:v:266:y:2018:i:2:p:609-621. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.