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

Algorithms for Queueing Systems with Reneging and Priorities Modeled as Quasi-Birth-Death Processes

Author

Listed:
  • Amir Rastpour

    (Faculty of Business and Information Technology, Ontario Tech University, Oshawa, Ontario L1H 7K5, Canada)

  • Armann Ingolfsson

    (Alberta School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada)

  • Burhaneddin Sandıkçı

    (Department of Industrial Engineering, Istanbul Technical University, 34367 Istanbul, Turkey)

Abstract

We consider a Markovian multiserver queueing system with two customer classes, preemptive priorities, and reneging. We formulate this system as an infinite level-dependent quasi-birth-death process (LDQBD). We introduce an algorithm that endogenously truncates the level and calculates lower and upper bounds on stationary probabilities of this LDQBD such that the gap between the bounds can be any desired amount. Our algorithm can be applied to any LDQBD for which the rate matrices become elementwise nonincreasing above some level. This appears to be the first algorithm that provides bounds on stationary probabilities for an infinite-level LDQBD. To obtain these bounds, the algorithm first obtains lower and upper bounds on the rate matrices of the LDQBD using a novel method, which can be applied to any LDQBD. We then extend this algorithm to approximate performance measures of the system of interest and calculate exact lower and upper bounds for those that can be expressed as probabilities, such as the probability that an incoming low-priority customer will wait. We generate a wide range of instances with up to 100 servers and compare the solution times and accuracy of our algorithm with two existing algorithms. These numerical experiments indicate that our algorithm is faster than the other two algorithms for a given accuracy requirement. We investigate the impact of changing service rates on the proportion of low-priority customers served and their wait time, and we demonstrate how ignoring one of these measures can possibly mislead decision makers. Summary of Contribution: We contribute to operations research by modeling a practically important queueing system and developing an algorithm to accurately compute performance measures for that system. We also contribute to computer science by providing error and complexity analysis for the algorithm to solve a broad class of two-dimensional Markov chains with infinite state space.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:orijoc:v:34:y:2022:i:3:p:1693-1710
    DOI: 10.1287/ijoc.2021.1141
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.1141
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2021.1141?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. Armann Ingolfsson & Ling Tang, 2012. "Efficient and Reliable Computation of Birth-Death Process Performance Measures," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 29-41, February.
    2. Douglas R. Miller, 1981. "Computation of Steady-State Probabilities for M / M /1 Priority Queues," Operations Research, INFORMS, vol. 29(5), pages 945-958, October.
    3. Mohammad Delasay & Armann Ingolfsson & Bora Kolfal, 2016. "Modeling Load and Overwork Effects in Queueing Systems with Adaptive Service Rates," Operations Research, INFORMS, vol. 64(4), pages 867-885, August.
    4. Hendrik Baumann & Werner Sandmann, 2016. "Structured Modeling and Analysis of Stochastic Epidemics with Immigration and Demographic Effects," PLOS ONE, Public Library of Science, vol. 11(3), pages 1-19, March.
    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. 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.

    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. Yutaka Sakuma & Onno Boxma & Tuan Phung-Duc, 2021. "An M/PH/1 queue with workload-dependent processing speed and vacations," Queueing Systems: Theory and Applications, Springer, vol. 98(3), pages 373-405, August.
    2. 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.
    3. Winfried K. Grassmann & Steve Drekic, 2008. "Multiple Eigenvalues in Spectral Analysis for Solving QBD Processes," Methodology and Computing in Applied Probability, Springer, vol. 10(1), pages 73-83, March.
    4. Jayaswal, Sachin & Vidyarthi, Navneet, 2013. "Capacitated Multiple Allocation Hub Location with Service Level Constraints for Multiple Consignment Classes," IIMA Working Papers WP2013-11-02, Indian Institute of Management Ahmedabad, Research and Publication Department.
    5. Jayaswal, Sachin & Jewkes, Elizabeth & Ray, Saibal, 2011. "Product differentiation and operations strategy in a capacitated environment," European Journal of Operational Research, Elsevier, vol. 210(3), pages 716-728, May.
    6. Hessam Bavafa & Anne Canamucio & Steven C. Marcus & Christian Terwiesch & Rachel M. Werner, 2022. "Capacity Rationing in Primary Care: Provider Availability Shocks and Channel Diversion," Management Science, INFORMS, vol. 68(4), pages 2842-2859, April.
    7. van Vianen, L.A. & Gabor, A.F. & van Ommeren, J.C.W., 2016. "Waiting times in classical priority queues via elementary lattice path counting," Econometric Institute Research Papers EI2016-17, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. William P. Barnett & Daniel A. Levinthal, 2017. "Special Issue Introduction: Evolutionary Logics of Strategy and Organization," Strategy Science, INFORMS, vol. 2(1), pages 1-1, March.
    9. Lars A. Vianen & Adriana F. Gabor & Jan-Kees Ommeren, 2016. "Waiting times in classical priority queues via elementary lattice path counting," Queueing Systems: Theory and Applications, Springer, vol. 84(3), pages 295-307, December.
    10. Philip A. Ernst & Søren Asmussen & John J. Hasenbein, 2018. "Stability and busy periods in a multiclass queue with state-dependent arrival rates," Queueing Systems: Theory and Applications, Springer, vol. 90(3), pages 207-224, December.
    11. William Liang & Barış Balcıog̃lu & Robert Svaluto, 2013. "Scheduling policies for a repair shop problem," Annals of Operations Research, Springer, vol. 211(1), pages 273-288, December.
    12. Vincent Huang & James Unwin, 2019. "Markov Chain Models of Refugee Migration Data," Papers 1903.08255, arXiv.org.
    13. Antonio Gómez-Corral & Martín López-García & Maria Jesus Lopez-Herrero & Diana Taipe, 2020. "On First-Passage Times and Sojourn Times in Finite QBD Processes and Their Applications in Epidemics," Mathematics, MDPI, vol. 8(10), pages 1-25, October.
    14. Mohammad Delasay & Armann Ingolfsson & Bora Kolfal, 2016. "Modeling Load and Overwork Effects in Queueing Systems with Adaptive Service Rates," Operations Research, INFORMS, vol. 64(4), pages 867-885, August.
    15. Jingqi Wang & Yong-Pin Zhou, 2018. "Impact of Queue Configuration on Service Time: Evidence from a Supermarket," Management Science, INFORMS, vol. 64(7), pages 3055-3075, July.
    16. Xu, Shuling & Hall, Nicholas G., 2021. "Fatigue, personnel scheduling and operations: Review and research opportunities," European Journal of Operational Research, Elsevier, vol. 295(3), pages 807-822.
    17. Attahiru Sule Alfa & Bin Liu & Qi‐Ming He, 2003. "Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(6), pages 662-682, September.
    18. Jillian A. Berry Jaeker & Anita L. Tucker, 2017. "Past the Point of Speeding Up: The Negative Effects of Workload Saturation on Efficiency and Patient Severity," Management Science, INFORMS, vol. 63(4), pages 1042-1062, April.
    19. Jianfu Wang & Opher Baron & Alan Scheller-Wolf, 2015. "M/M/c Queue with Two Priority Classes," Operations Research, INFORMS, vol. 63(3), pages 733-749, June.
    20. Jayaswal, Sachin & Vidyarthi, Navneet, 2023. "Multiple allocation hub location with service level constraints for two shipment classes," European Journal of Operational Research, Elsevier, vol. 309(2), pages 634-655.

    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:34:y:2022:i:3:p:1693-1710. 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.