Ergodic control of multi-class $M/M/N+M$ queues in the Halfin-Whitt regime

Abstract

We study a dynamic scheduling problem for a multi-class queueing network with a large pool of statistically identical servers. The arrival processes are Poisson, and service times and patience times are assumed to be exponentially distributed and class dependent. The optimization criterion is the expected long time average (ergodic) of a general (nonlinear) running cost function of the queue lengths. We consider this control problem in the Halfin-Whitt (QED) regime, that is, the number of servers $n$ and the total offered load $\mathbf{r}$ scale like $n\approx \mathbf{r}+\hat{\rho }\sqrt{\mathbf{r}}$ for some constant $\hat{\rho }$. This problem was proposed in [Ann. Appl. Probab. 14 (2004) 1084-1134, Section 5.2]. The optimal solution of this control problem can be approximated by that of the corresponding ergodic diffusion control problem in the limit. We introduce a broad class of ergodic control problems for controlled diffusions, which includes a large class of queueing models in the diffusion approximation, and establish a complete characterization of optimality via the study of the associated HJB equation. We also prove the asymptotic convergence of the values for the multi-class queueing control problem to the value of the associated ergodic diffusion control problem. The proof relies on an approximation method by spatial truncation for the ergodic control of diffusion processes, where the Markov policies follow a fixed priority policy outside a fixed compact set.

Published at http://dx.doi.org/10.1214/14-AAP1081 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Validity of heavy traffic steady-state approximations in generalized Jackson Networks
• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic
• Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic
• Diffusion models and steady-state approximations for exponentially ergodic Markovian queues
• Control of the multiclass $G/G/1$ queue in the moderate deviation regime

Cited by in corpus (9)

• Ergodicity of Lévy-driven SDEs arising from multiclass many-server queues
• Ergodic Diffusion Control of Multiclass Multi-Pool Networks in the Halfin-Whitt Regime
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime
• On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime
• Some new results on sample path optimality in ergodic control of diffusions
• Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
• Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment
• Exponential ergodicity and steady-state approximations for a class of Markov processes under fast regime switching