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

asymptotic optimalitydiffusion approximationergodic controlHalfin-Whitt regimelong time-average controlmulti-class Markovian queuesspatial truncationstable Markov optimal control

Mathematics Subject Classification ID

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

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

• 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 GI/GI/1+GI queue with multiple customer classes
• Dynamic Scheduling of a Multiclass Queue in the Halfin-Whitt Heavy Traffic Regime
• 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
• 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?)
• 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 ergodic stochastic control
• ON REGULARITY OF TRANSITION PROBABILITIES AND INVARIANT MEASURES OF SINGULAR DIFFUSIONS UNDER MINIMAL CONDITIONS
• On the asymptotic optimality of the c / 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 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
• Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule
• Statistical Analysis of a Telephone Call Center
• The c / rule for many-server queues with abandonment
• Validity of heavy traffic steady-state approximations in generalized Jackson networks

Cited in

(21)

• An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Uniform stability of some large-scale parallel server networks
• 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
• Uniform polynomial rates of convergence for a class of Lévy-driven controlled SDEs arising in multiclass many-server queues
• 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
• Simplified control problems for multiclass many-server queueing 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
• On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime
• 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
• Delay-based service differentiation with many servers and time-varying arrival rates
• Optimal control of Markov-modulated multiclass many-server queues
• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime
• Two‐class constrained optimization with applications to queueing control
• Ergodic risk sensitive control of Markovian multiclass many-server queues with abandonment
• Control of the multiclass \(\mathrm{G}/\mathrm{G}/1\) queue in the moderate deviation regime

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)