Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic
Open Access
- 1 August 2004
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 14 (3), 1084-1134
- https://doi.org/10.1214/105051604000000233
Abstract
We consider the problem of scheduling a queueing system in which many statistically identical servers cater to several classes of impatient customers. Service times and impatience clocks are exponential while arrival processes are renewal. Our cost is an expected cumulative discounted function, linear or nonlinear, of appropriately normalized performance measures. As a special case, the cost per unit time can be a function of the number of customers waiting to be served in each class, the number actually being served, the abandonment rate, the delay experienced by customers, the number of idling servers, as well as certain combinations thereof. We study the system in an asymptotic heavy-traffic regime where the number of servers n and the offered load r are simultaneously scaled up and carefully balanced: for some scalar β. This yields an operation that enjoys the benefits of both heavy traffic (high server utilization) and light traffic (high service levels.) We first consider a formal weak limit, through which our queueing scheduling problem gives rise to a diffusion control problem. We show that the latter has an optimal Markov control policy, and that the corresponding Hamilton–Jacobi–Bellman (HJB) equation has a unique classical solution. The Markov control policy and the HJB equation are then used to define scheduling control policies which we prove are asymptotically optimal for our original queueing system. The analysis yields both qualitative and quantitative insights, in particular on staffing levels, the roles of non-preemption and work conservation, and the trade-off between service quality and servers’ efficiency.Keywords
This publication has 30 references indexed in Scilit:
- Some diffusion approximations with state space collapsePublished by Springer Science and Business Media LLC ,2005
- A Brownian control problem for a simple queueing system in the Halfin–Whitt regimeSystems & Control Letters, 2004
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policyThe Annals of Applied Probability, 2001
- Two-server closed networks in heavy traffic: diffusion limits and asymptotic optimalityThe Annals of Applied Probability, 2000
- Dynamic control of Brownian networks: state space collapse and equivalent workload formulationsThe Annals of Applied Probability, 1997
- Dynamic Scheduling with Convex Delay Costs: The Generalized $c|mu$ RuleThe Annals of Applied Probability, 1995
- Diffusion approximation forGI/G/1 controlled queuesQueueing Systems, 1992
- Weak Limit Theorems for Stochastic Integrals and Stochastic Differential EquationsThe Annals of Probability, 1991
- On uniqueness and existence of viscosity solutions of fully nonlinear second‐order elliptic PDE'sCommunications on Pure and Applied Mathematics, 1989
- The Equivalence of Functional Central Limit Theorems for Counting Processes and Associated Partial SumsThe Annals of Mathematical Statistics, 1971