IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v57y2009i4p975-989.html
   My bibliography  Save this article

Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations

Author

Listed:
  • K. D. Glazebrook

    (Department of Mathematics and Statistics, and Department of Management Science, Lancaster University, Lancaster, LA1 4YX, United Kingdom)

  • C. Kirkbride

    (Department of Management Science, Lancaster University, Lancaster, LA1 4YX, United Kingdom)

  • J. Ouenniche

    (Business School, University of Edinburgh, Edinburgh, EH8 9JY, United Kingdom)

Abstract

We propose a general Markovian model for the optimal control of admissions and subsequent routing of customers for service provided by a collection of heterogeneous stations. Queue-length information is available to inform all decisions. Admitted customers will abandon the system if required to wait too long for service. The optimisation goal is the maximisation of reward rate earned from service completions, net of the penalties paid whenever admission is denied, and the costs incurred upon every customer loss through impatience. We show that the system is indexable under mild conditions on model parameters and give an explicit construction of an index policy for admission control and routing founded on a proposal of Whittle for restless bandits. We are able to gain insights regarding the strength of performance of the index policy from the nature of solutions to the Lagrangian relaxation used to develop the indices. These insights are strengthened by the development of performance bounds. Although we are able to assert the optimality of the index heuristic in a range of asymptotic regimes, the performance bounds are also able to identify instances where its performance is relatively weak. Numerical studies are used to illustrate and support the theoretical analyses.

Suggested Citation

  • K. D. Glazebrook & C. Kirkbride & J. Ouenniche, 2009. "Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations," Operations Research, INFORMS, vol. 57(4), pages 975-989, August.
  • Handle: RePEc:inm:oropre:v:57:y:2009:i:4:p:975-989
    DOI: 10.1287/opre.1080.0632
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0632
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1080.0632?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. Shlomo Halfin & Ward Whitt, 1981. "Heavy-Traffic Limits for Queues with Many Exponential Servers," Operations Research, INFORMS, vol. 29(3), pages 567-588, June.
    2. J. Michael Harrison & Assaf Zeevi, 2004. "Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime," Operations Research, INFORMS, vol. 52(2), pages 243-257, April.
    3. Glazebrook, K. D. & Mitchell, H. M. & Ansell, P. S., 2005. "Index policies for the maintenance of a collection of machines by a set of repairmen," European Journal of Operational Research, Elsevier, vol. 165(1), pages 267-284, August.
    4. Christos H. Papadimitriou & John N. Tsitsiklis, 1999. "The Complexity of Optimal Queuing Network Control," Mathematics of Operations Research, INFORMS, vol. 24(2), pages 293-305, May.
    5. Kevin D. Glazebrook & José Niño-Mora, 2001. "Parallel Scheduling of Multiclass M/M/m Queues: Approximate and Heavy-Traffic Optimization of Achievable Performance," Operations Research, INFORMS, vol. 49(4), pages 609-623, August.
    6. Dimitris Bertsimas & José Niño-Mora, 1996. "Conservation Laws, Extended Polymatroids and Multiarmed Bandit Problems; A Polyhedral Approach to Indexable Systems," Mathematics of Operations Research, INFORMS, vol. 21(2), pages 257-306, 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. Ece Zeliha Demirci & Joachim Arts & Geert-Jan Van Houtum, 2022. "A restless bandit approach for capacitated condition based maintenance scheduling," DEM Discussion Paper Series 22-01, Department of Economics at the University of Luxembourg.
    2. Dong Li & Kevin D. Glazebrook, 2010. "An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(3), pages 225-236, April.
    3. Urtzi Ayesta & Manu K. Gupta & Ina Maria Verloop, 2021. "On the computation of Whittle’s index for Markovian restless bandits," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(1), pages 179-208, February.
    4. 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.
    5. Ford, Stephen & Atkinson, Michael P. & Glazebrook, Kevin & Jacko, Peter, 2020. "On the dynamic allocation of assets subject to failure," European Journal of Operational Research, Elsevier, vol. 284(1), pages 227-239.
    6. Kyle Y. Lin & Michael P. Atkinson & Timothy H. Chung & Kevin D. Glazebrook, 2013. "A Graph Patrol Problem with Random Attack Times," Operations Research, INFORMS, vol. 61(3), pages 694-710, June.
    7. Nicolas Gast & Bruno Gaujal & Kimang Khun, 2023. "Testing indexability and computing Whittle and Gittins index in subcubic time," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 97(3), pages 391-436, June.
    8. S. Duran & U. Ayesta & I. M. Verloop, 2022. "On the Whittle index of Markov modulated restless bandits," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 373-430, December.
    9. Vivek S. Borkar & Sarath Pattathil, 2022. "Whittle indexability in egalitarian processor sharing systems," Annals of Operations Research, Springer, vol. 317(2), pages 417-437, October.
    10. Turgay Ayer & Can Zhang & Anthony Bonifonte & Anne C. Spaulding & Jagpreet Chhatwal, 2019. "Prioritizing Hepatitis C Treatment in U.S. Prisons," Operations Research, INFORMS, vol. 67(3), pages 853-873, 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. José Niño-Mora, 2006. "Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 50-84, February.
    2. Dong Li & Li Ding & Stephen Connor, 2020. "When to Switch? Index Policies for Resource Scheduling in Emergency Response," Production and Operations Management, Production and Operations Management Society, vol. 29(2), pages 241-262, February.
    3. Amy R. Ward & Mor Armony, 2013. "Blind Fair Routing in Large-Scale Service Systems with Heterogeneous Customers and Servers," Operations Research, INFORMS, vol. 61(1), pages 228-243, February.
    4. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    5. José Niño-Mora, 2020. "Fast Two-Stage Computation of an Index Policy for Multi-Armed Bandits with Setup Delays," Mathematics, MDPI, vol. 9(1), pages 1-36, December.
    6. Achal Bassamboo & Assaf Zeevi, 2009. "On a Data-Driven Method for Staffing Large Call Centers," Operations Research, INFORMS, vol. 57(3), pages 714-726, June.
    7. Ari Arapostathis & Hassan Hmedi & Guodong Pang, 2021. "On Uniform Exponential Ergodicity of Markovian Multiclass Many-Server Queues in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 772-796, May.
    8. R. T. Dunn & K. D. Glazebrook, 2004. "Discounted Multiarmed Bandit Problems on a Collection of Machines with Varying Speeds," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 266-279, May.
    9. Turgay Ayer & Can Zhang & Anthony Bonifonte & Anne C. Spaulding & Jagpreet Chhatwal, 2019. "Prioritizing Hepatitis C Treatment in U.S. Prisons," Operations Research, INFORMS, vol. 67(3), pages 853-873, May.
    10. Itay Gurvich & Ward Whitt, 2009. "Scheduling Flexible Servers with Convex Delay Costs in Many-Server Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 237-253, June.
    11. Noah Gans & Yong-Pin Zhou, 2007. "Call-Routing Schemes for Call-Center Outsourcing," Manufacturing & Service Operations Management, INFORMS, vol. 9(1), pages 33-50, May.
    12. Opher Baron & Joseph Milner, 2009. "Staffing to Maximize Profit for Call Centers with Alternate Service-Level Agreements," Operations Research, INFORMS, vol. 57(3), pages 685-700, June.
    13. Constantinos Maglaras & Assaf Zeevi, 2004. "Diffusion Approximations for a Multiclass Markovian Service System with “Guaranteed” and “Best-Effort” Service Levels," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 786-813, November.
    14. Tolga Tezcan & J. G. Dai, 2010. "Dynamic Control of N -Systems with Many Servers: Asymptotic Optimality of a Static Priority Policy in Heavy Traffic," Operations Research, INFORMS, vol. 58(1), pages 94-110, February.
    15. Eugene Furman & Adam Diamant & Murat Kristal, 2021. "Customer Acquisition and Retention: A Fluid Approach for Staffing," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4236-4257, November.
    16. Avishai Mandelbaum & Petar Momčilović, 2008. "Queues with Many Servers: The Virtual Waiting-Time Process in the QED Regime," Mathematics of Operations Research, INFORMS, vol. 33(3), pages 561-586, August.
    17. Noa Zychlinski, 2023. "Applications of fluid models in service operations management," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 161-185, February.
    18. Dongyuan Zhan & Amy R. Ward, 2014. "Threshold Routing to Trade Off Waiting and Call Resolution in Call Centers," Manufacturing & Service Operations Management, INFORMS, vol. 16(2), pages 220-237, May.
    19. Constantinos Maglaras & Assaf Zeevi, 2005. "Pricing and Design of Differentiated Services: Approximate Analysis and Structural Insights," Operations Research, INFORMS, vol. 53(2), pages 242-262, April.
    20. Terry James & Kevin Glazebrook & Kyle Lin, 2016. "Developing Effective Service Policies for Multiclass Queues with Abandonment: Asymptotic Optimality and Approximate Policy Improvement," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 251-264, May.

    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:oropre:v:57:y:2009:i:4:p:975-989. 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.