Containment of socially optimal policies in multiple-facility Markovian queueing systems

• Published in: The Journal of the Operational Research Society 2016-04, Vol.67 (4), p.629-643
• Main Authors: Shone, Rob, Knight, Vincent A, Harper, Paul R, Williams, Janet E, Minty, John
• Format: Article
• Language: English
• Subjects: Business and Management; Carrying costs; Costs; Customer services; Decision making; Dynamic programming; equilibrium strategies; General Paper; Management; Markov chains; Markov Decision Processes; Markov processes; Mathematical vectors; Open; Operations research; Operations Research/Decision Theory; Optimal policy; optimal strategies; Optimization; Queueing theory; queues with balking; Queuing; Servers; Social classes; Steady states; Studies; Systems stability; Unobservables
• ISSN: 0160-5682; 1476-9360
• DOI: 10.1057/jors.2015.98

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as 'selfishly optimal' and 'socially optimal'. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.