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

DOI10.1214/14-AAP1081MaRDI QIDQ894815zbMATH OpenOpenAlexWikidataFDO

Authors Anup Biswas, Guodong Pang, Ari Arapostathis

Publication date 24 November 2015

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.1957, https://projecteuclid.org/euclid.aoap/1443703781

zbMATH Keywords

diffusion approximationHalfin-Whitt regimeergodic controlasymptotic optimalityspatial truncationstable Markov optimal controllong time-average controlmulti-class Markovian queues

Mathematics Subject Classification ID

Diffusion processes (60J60) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Optimal stochastic control (93E20) Stochastic scheduling theory in operations research (90B36)

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 $mathbfr$ scale like $napproxmathbfr+hathosqrtmathbfr$ for some constant $hatho$. 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.

Recommendations

• Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime
• An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
• Simplified control problems for multiclass many-server queueing systems
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 3678487 (Why is no real title available?)
• scientific article; zbMATH DE number 3720745 (Why is no real title available?)
• scientific article; zbMATH DE number 42423 (Why is no real title available?)
• scientific article; zbMATH DE number 1417210 (Why is no real title available?)
• scientific article; zbMATH DE number 3895476 (Why is no real title available?)
• Admission control for a multi-server queue with abandonment
• Control of the multiclass \(\mathrm{G}/\mathrm{G}/1\) queue in the moderate deviation regime
• Degenerate variance control in the one-dimensional stationary case
• Diffusion models and steady-state approximations for exponentially ergodic Markovian queues
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• Dynamic scheduling of a GI/GI/1+GI queue with multiple customer classes
• Dynamic scheduling with convex delay costs: The generalized \(c\mu\) rule
• Ergodic control of diffusion processes.
• Ergodic rate control problem for single class queueing networks
• Existence of strong solutions for Itô's stochastic equations via approximations
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Large time behavior of solutions of Hamilton-Jacobi-Bellman equations with quadratic nonlinearity in gradients
• 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 REGULARITY OF TRANSITION PROBABILITIES AND INVARIANT MEASURES OF SINGULAR DIFFUSIONS UNDER MINIMAL CONDITIONS
• On ergodic stochastic control
• On the asymptotic optimality of the \(c \mu / \theta \) rule under ergodic cost
• Optimal control of parallel server systems with many servers in heavy traffic
• Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions
• Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic.
• Scheduling control for Markov-modulated single-server multiclass queueing systems in heavy traffic
• Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic
• Statistical Analysis of a Telephone Call Center
• The \(c\mu /\theta \) rule for many-server queues with abandonment
• Validity of heavy traffic steady-state approximations in generalized Jackson networks

Cited in

(20)

• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime
• Optimal scheduling of critically loaded multiclass \(GI/m/n+m\) queues in an alternating renewal environment
• Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic
• A Brownian control problem for a simple queueing system in the halfin--whitt regime
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• Control of the multiclass \(\mathrm{G}/\mathrm{G}/1\) queue in the moderate deviation regime
• Delay-based service differentiation with many servers and time-varying arrival rates
• Exponential ergodicity and steady-state approximations for a class of Markov processes under fast regime switching
• Optimal sizing of the sediment replenishment capacity based on robust ergodic control of subordinator-driven dynamics
• Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime
• Optimal control of Markov-modulated multiclass many-server queues
• Two‐class constrained optimization with applications to queueing control
• An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
• Simplified control problems for multiclass many-server queueing systems
• On uniform exponential ergodicity of Markovian multiclass many-server 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
• Uniform stability of some large-scale parallel server networks

This page was built for publication: Ergodic control of multi-class \(\mathrm{M}/\mathrm{M}/N+\mathrm{M}\) 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 Q894815)