IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v317y2022i2d10.1007_s10479-019-03131-3.html
   My bibliography  Save this article

K competing queues with customer abandonment: optimality of a generalised $$c \mu $$ c μ -rule by the Smoothed Rate Truncation method

Author

Listed:
  • S. Bhulai

    (Vrije Universiteit Amsterdam)

  • H. Blok

    (Eindhoven University of Technology)

  • F. M. Spieksma

    (Universiteit Leiden)

Abstract

We consider a K-competing queues system with the additional feature of customer abandonment. Without abandonment, it is optimal to allocate the server to a queue according to the $$c \mu $$ c μ -rule. To derive a similar rule for the system with abandonment, we model the system as a continuous-time Markov decision process. Due to impatience, the Markov decision process has unbounded jump rates as a function of the state. Hence it is not uniformisable, and so far there has been no systematic direct way to analyse this. The Smoothed Rate Truncation principle is a technique designed to make an unbounded rate process uniformisable, while preserving the properties of interest. Together with theory securing continuity in the limit, this provides a framework to analyse unbounded rate Markov decision processes. With this approach, we have been able to find close-fitting conditions guaranteeing optimality of a strict priority rule.

Suggested Citation

  • S. Bhulai & H. Blok & F. M. Spieksma, 2022. "K competing queues with customer abandonment: optimality of a generalised $$c \mu $$ c μ -rule by the Smoothed Rate Truncation method," Annals of Operations Research, Springer, vol. 317(2), pages 387-416, October.
  • Handle: RePEc:spr:annopr:v:317:y:2022:i:2:d:10.1007_s10479-019-03131-3
    DOI: 10.1007/s10479-019-03131-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03131-3
    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/s10479-019-03131-3?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. Richard F. Serfozo, 1979. "Technical Note—An Equivalence Between Continuous and Discrete Time Markov Decision Processes," Operations Research, INFORMS, vol. 27(3), pages 616-620, June.
    2. H. Blok & F. M. Spieksma, 2017. "Structures of Optimal Policies in MDPs with Unbounded Jumps: The State of Our Art," International Series in Operations Research & Management Science, in: Richard J. Boucherie & Nico M. van Dijk (ed.), Markov Decision Processes in Practice, chapter 0, pages 131-186, Springer.
    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. Dwi Ertiningsih & Sandjai Bhulai & Flora Spieksma, 2018. "A novel use of value iteration for deriving bounds for threshold and switching curve optimal policies," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(8), pages 638-659, December.
    2. Xiuli Chao & Frank Y. Chen, 2005. "An Optimal Production and Shutdown Strategy when a Supplier Offers an Incentive Program," Manufacturing & Service Operations Management, INFORMS, vol. 7(2), pages 130-143, March.
    3. Nicole Leder & Bernd Heidergott & Arie Hordijk, 2010. "An Approximation Approach for the Deviation Matrix of Continuous-Time Markov Processes with Application to Markov Decision Theory," Operations Research, INFORMS, vol. 58(4-part-1), pages 918-932, August.
    4. Dinard van der Laan, 2015. "Assigning Multiple Job Types to Parallel Specialized Servers," Tinbergen Institute Discussion Papers 15-102/III, Tinbergen Institute.
    5. Sergei V. Savin & Morris A. Cohen & Noah Gans & Ziv Katalan, 2005. "Capacity Management in Rental Businesses with Two Customer Bases," Operations Research, INFORMS, vol. 53(4), pages 617-631, August.
    6. Xufeng Yang & Juliang Zhang & Wen Jiao & Hong Yan, 2023. "Optimal Capacity Rationing Policy for a Container Leasing System with Multiple Kinds of Customers and Substitutable Containers," Management Science, INFORMS, vol. 69(3), pages 1468-1485, March.
    7. Han, Gain & Sohn, Keemin, 2016. "Activity imputation for trip-chains elicited from smart-card data using a continuous hidden Markov model," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 121-135.
    8. Gregory Dobson & Hsiao-Hui Lee & Arvind Sainathan & Vera Tilson, 2012. "A Queueing Model to Evaluate the Impact of Patient "Batching" on Throughput and Flow Time in a Medical Teaching Facility," Manufacturing & Service Operations Management, INFORMS, vol. 14(4), pages 584-599, October.
    9. Yoon, Soovin & Albert, Laura A., 2020. "A dynamic ambulance routing model with multiple response," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    10. Lode Li & Evan L. Porteus & Hongtao Zhang, 2001. "Optimal Operating Policies for Multiplant Stochastic Manufacturing Systems in a Changing Environment," Management Science, INFORMS, vol. 47(11), pages 1539-1551, November.
    11. Allahviranloo, Mahdieh & Recker, Will, 2013. "Daily activity pattern recognition by using support vector machines with multiple classes," Transportation Research Part B: Methodological, Elsevier, vol. 58(C), pages 16-43.
    12. Gabriel Zayas‐Cabán & Emmett J. Lodree & David L. Kaufman, 2020. "Optimal Control of Parallel Queues for Managing Volunteer Convergence," Production and Operations Management, Production and Operations Management Society, vol. 29(10), pages 2268-2288, October.
    13. Alexander Zadorojniy & Guy Even & Adam Shwartz, 2009. "A Strongly Polynomial Algorithm for Controlled Queues," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 992-1007, November.
    14. Hui Zhao & Vinayak Deshpande & Jennifer K. Ryan, 2006. "Emergency transshipment in decentralized dealer networks: When to send and accept transshipment requests," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(6), pages 547-567, September.
    15. I. M. MacPhee & L. J. Müller, 2007. "Stability Criteria for Multi-class Queueing Networks with Re-entrant Lines," Methodology and Computing in Applied Probability, Springer, vol. 9(3), pages 377-388, September.
    16. Waal, P.R. & Dijk, N.M. van, 1988. "Monotonicity of performance measures in a processor sharing queue," Serie Research Memoranda 0051, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    17. Sobel, Matthew J. & Szmerekovsky, Joseph G. & Tilson, Vera, 2009. "Scheduling projects with stochastic activity duration to maximize expected net present value," European Journal of Operational Research, Elsevier, vol. 198(3), pages 697-705, November.
    18. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    19. Epaminondas G. Kyriakidis & Theodosis D. Dimitrakos, 2005. "Computation of the Optimal Policy for the Control of a Compound Immigration Process through Total Catastrophes," Methodology and Computing in Applied Probability, Springer, vol. 7(1), pages 97-118, March.
    20. Rob Shone & Vincent A. Knight & Paul R. Harper, 2020. "A conservative index heuristic for routing problems with multiple heterogeneous service facilities," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(3), pages 511-543, December.

    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:annopr:v:317:y:2022:i:2:d:10.1007_s10479-019-03131-3. 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.