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

K. Glazebrook, C. Kirkbride, J. Ouenniche

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)975-989
Number of pages15
JournalOperations Research
Issue number4
Publication statusPublished - Jul 2009

Keywords / Materials (for Non-textual outputs)

  • admission control
  • customer impatience
  • dynamic programming
  • index policies
  • Markov decision processes
  • monotone policies
  • restless bandits
  • routing


Dive into the research topics of 'Index Policies for the Admission Control and Routing of Impatient Customers to Heterogeneous Service Stations'. Together they form a unique fingerprint.

Cite this