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

DOI10.1287/MOOR.2020.1087zbMATH Open1468.90039arXiv1812.03528OpenAlexW3127315825WikidataQ115516199 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

• Ergodic control of diffusion processes.
• Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Computable bounds for geometric convergence rates of Markov chains
• Steady-state analysis of a multiserver queue in the Halfin-Whitt regime
• Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
• Steady-state GI/G/\(n\) queue in the Halfin-Whitt regime
• Tightness of invariant distributions of a large-scale flexible service system under a priority discipline
• Diffusion-Scale Tightness of Invariant Distributions of a Large-Scale Flexible Service System
• Existence of strong solutions for Itô's stochastic equations via approximations
• Stein's method for steady-state diffusion approximations of \(\mathrm{M}/\mathrm{Ph}/n+\mathrm{M}\) systems
• State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic
• Understanding the Efficiency of Multi-Server Service Systems
• Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions
• Validity of heavy traffic steady-state approximations in generalized Jackson networks
• Systems with large flexible server pools: instability of ``natural load balancing
• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic.
• Stationary distribution convergence for generalized Jackson networks in heavy traffic
• On the use of Lyapunov methods in renewal theory
• Validity of heavy-traffic steady-state approximations in many-server queues with abandonment
• Many-server queues with customer abandonment: numerical analysis of their diffusion models
• Validity of Heavy-Traffic Steady-State Approximations in Multiclass Queueing Networks: The Case of Queue-Ratio Disciplines
• Convergence of the Relative Value Iteration for the Ergodic Control Problem of Nondegenerate Diffusions under Near-Monotone Costs
• 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
• Ergodic control of multi-class \(\mathrm{M}/\mathrm{M}/N+\mathrm{M}\) queues in the Halfin-Whitt regime
• Stein's method for steady-state diffusion approximations: an introduction through the Erlang-A and Erlang-C models
• Justifying diffusion approximations for multiclass queueing networks under a moment condition
• Diffusion limit of fair resource control -- stationarity and interchange of limits
• Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime
• Ergodicity of an SPDE associated with a many-server queue
• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• The Limit of Stationary Distributions of Many-Server Queues in the Halfin–Whitt Regime
• Infinite-Horizon Average Optimality of the N-Network in the Halfin–Whitt Regime

Cited In (6)

• Exponential ergodicity and steady-state approximations for a class of markov processes under fast regime switching
• 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
• On the global convergence of relative value iteration for infinite-horizon risk-sensitive control of diffusions
• 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)