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

DOI10.1214/14-AAP1081zbMATH Open1330.60108arXiv1404.1957OpenAlexW1868692815WikidataQ60167476 ScholiaQ60167476MaRDI QIDQ894815FDOQ894815

Authors: Anup Biswas, Guodong Pang, Ari Arapostathis 

Publication date: 24 November 2015

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

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.

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

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

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)

Cites Work

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

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
• Two‐class constrained optimization with applications to queueing control
• Optimal control of Markov-modulated multiclass many-server queues
• 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)