On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime

DOI10.1287/MOOR.2020.1087zbMATH Open1468.90039OpenAlexW3127315825WikidataQ115516199 ScholiaQ115516199MaRDI QIDQ5000654FDOQ5000654

Authors: Hassan Hmedi, Guodong Pang, Ari Arapostathis 

Publication date: 15 July 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: We study ergodic properties of Markovian multiclass many-server queues which are uniform over scheduling policies, as well as the size n of the system. The system is heavily loaded in the Halfin-Whitt regime, and the scheduling policies are work-conserving and preemptive. We provide a unified approach via a Lyapunov function method that establishes Foster-Lyapunov equations for both the limiting diffusion and the prelimit diffusion-scaled queueing processes simultaneously. We first study the limiting controlled diffusion, and we show that if the spare capacity (safety staffing) parameter is positive, then the diffusion is exponentially ergodic uniformly over all stationary Markov controls, and the invariant probability measures have uniform exponential tails. This result is sharp, since when there is no abandonment and the spare capacity parameter is negative, then the controlled diffusion is transient under any Markov control. In addition, we show that if all the abandonment rates are positive, the invariant probability measures have sub-Gaussian tails, regardless whether the spare capacity parameter is positive or negative. Using the above results, we proceed to establish the corresponding ergodic properties for the diffusion-scaled queueing processes. In addition to providing a simpler proof of the results in Gamarnik and Stolyar [Queueing Syst (2012) 71:25-51], we extend these results to the multiclass models with renewal arrival processes, albeit under the assumption that the mean residual life functions are bounded. For the Markovian model with Poisson arrivals, we obtain stronger results and show that the convergence to the stationary distribution is at an exponential rate uniformly over all work-conserving stationary Markov scheduling policies.

Full work available at URL: https://arxiv.org/abs/1812.03528

Recommendations

• Optimal control of Markov-modulated multiclass many-server queues
• Ergodic control of multi-class \(\mathrm{M}/\mathrm{M}/N+\mathrm{M}\) queues in the Halfin-Whitt regime
• Uniform polynomial rates of convergence for a class of Lévy-driven controlled SDEs arising in multiclass many-server queues
• The limit of stationary distributions of many-server queues in the Halfin-Whitt regime
• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues

zbMATH Keywords

Halfin-Whitt (QED) regimediffusion scalinguniform exponential ergodicitymulticlass many-server queues

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15) Stochastic scheduling theory in operations research (90B36)

Cites Work

• Computable bounds for geometric convergence rates of Markov chains
• Convergence of the relative value iteration for the ergodic control problem of nondegenerate diffusions under near-monotone costs
• Diffusion limit of fair resource control -- stationarity and interchange of limits
• Diffusion-scale tightness of invariant distributions of a large-scale flexible service system
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• Ergodic control of diffusion processes.
• Ergodic control of multi-class \(\mathrm{M}/\mathrm{M}/N+\mathrm{M}\) queues in the Halfin-Whitt regime
• Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime
• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Ergodicity of an SPDE associated with a many-server queue
• Existence of strong solutions for Itô's stochastic equations via approximations
• Harnack inequalities for solutions of general second order parabolic equations and estimates of their Hölder constants
• Heavy traffic approximation for the stationary distribution of a generalized Jackson network: the BAR approach
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime
• Justifying diffusion approximations for multiclass queueing networks under a moment condition
• Many-server queues with customer abandonment: numerical analysis of their diffusion model
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
• On the use of Lyapunov methods in renewal theory
• Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions
• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic.
• Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
• State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic
• Stationary distribution convergence for generalized Jackson networks in heavy traffic
• Steady-state GI/G/\(n\) queue in the Halfin-Whitt regime
• Steady-state analysis of a multiserver queue in the Halfin-Whitt regime
• Stein's method for steady-state diffusion approximations of \(\mathrm{M}/\mathrm{Ph}/n+\mathrm{M}\) systems
• Stein's method for steady-state diffusion approximations: an introduction through the Erlang-A and Erlang-C models
• Systems with large flexible server pools: instability of ``natural load balancing
• The limit of stationary distributions of many-server queues in the Halfin-Whitt regime
• Tightness of invariant distributions of a large-scale flexible service system under a priority discipline
• Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime
• Understanding the Efficiency of Multi-Server Service Systems
• Validity of heavy traffic steady-state approximations in generalized Jackson networks
• Validity of heavy-traffic steady-state approximations in many-server queues with abandonment
• Validity of heavy-traffic steady-state approximations in multiclass queueing networks: the case of queue-ratio disciplines

Cited In (13)

• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Ergodicity of an SPDE associated with a many-server queue
• On System-Wide Safety Staffing of Large-Scale Parallel Server Networks
• Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
• A variational characterization of the optimal exit rate for controlled diffusions
• Subexponential upper and lower bounds in Wasserstein distance for Markov processes
• Exponential upper bounds via martingales for multiplexers with Markovian arrivals
• Exponential ergodicity and steady-state approximations for a class of Markov processes under fast regime switching
• On the global convergence of relative value iteration for infinite-horizon risk-sensitive control of diffusions
• Optimal control of Markov-modulated multiclass many-server queues
• Spectral gap of the Erlang A model in the Halfin-Whitt regime
• Uniform polynomial rates of convergence for a class of Lévy-driven controlled SDEs arising in multiclass many-server queues
• Uniform stability of some large-scale parallel server networks

This page was built for publication: On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000654)