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

K. D. Glazebrook (), C. Kirkbride () and J. Ouenniche ()
Additional contact information
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

Operations Research, 2009, vol. 57, issue 4, 975-989

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.

Keywords: admission control; customer impatience; dynamic programming; index policies; Markov decision processes; monotone policies; restless bandits; routing (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0632 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:57:y:2009:i:4:p:975-989

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().