Infinite horizon asymptotic average optimality for large-scale parallel server networks

DOI10.1016/J.SPA.2018.03.005zbMATH Open1404.60134arXiv1706.03931OpenAlexW2732160403WikidataQ60167459 ScholiaQ60167459MaRDI QIDQ1756967FDOQ1756967

Authors: Guodong Pang, Ari Arapostathis 

Publication date: 28 December 2018

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: We study infinite-horizon asymptotic average optimality for parallel server network with multiple classes of jobs and multiple server pools in the Halfin-Whitt regime. Three control formulations are considered: 1) minimizing the queueing and idleness cost, 2) minimizing the queueing cost under a constraints on idleness at each server pool, and 3) fairly allocating the idle servers among different server pools. For the third problem, we consider a class of bounded-queue, bounded-state (BQBS) stable networks, in which any moment of the state is bounded by that of the queue only (for both the limiting diffusion and diffusion-scaled state processes). We show that the optimal values for the diffusion-scaled state processes converge to the corresponding values of the ergodic control problems for the limiting diffusion. We present a family of state-dependent Markov balanced saturation policies (BSPs) that stabilize the controlled diffusion-scaled state processes. It is shown that under these policies, the diffusion-scaled state process is exponentially ergodic, provided that at least one class of jobs has a positive abandonment rate. We also establish useful moment bounds, and study the ergodic properties of the diffusion-scaled state processes, which play a crucial role in proving the asymptotic optimality.

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

Recommendations

• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime
• Server optimization of infinite queueing systems
• Scheduling parallel servers in the nondegenerate slowdown diffusion regime: asymptotic optimality results
• Optimal server allocation in general, finite, multi-server queueing networks
• Asymptotically maximal throughput in tandem systems with flexible and dedicated servers
• Asymptotic optimality of power-of-\(d\) load balancing in large-scale systems
• HEAVY TRAFFIC APPROXIMATIONS FOR A SYSTEM OF INFINITE SERVERS WITH LOAD BALANCING
• Optimal routing to parallel heterogeneous servers-small arrival rates
• Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies

zbMATH Keywords

fairnessexponential stabilityasymptotic optimalityHalfin-Whitt (QED) regimemulticlass multi-pool Markovian queuesbalanced saturation policy (BSP)bounded-queue bounded-state (BQBS) stable networksergodic control (with constraints)

Mathematics Subject Classification ID

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) Stochastic scheduling theory in operations research (90B36)

Cites Work

• Title not available (Why is that?)
• Stochastic-Process Limits
• Title not available (Why is that?)
• Heavy-traffic limits for a many-server queueing network with switchover
• Multiclass multiserver queueing system in the Halfin-Whitt heavy traffic regime: asymptotics of the stationary distribution
• 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
• Blind fair routing in large-scale service systems with heterogeneous customers and servers
• Subgeometric rates of convergence of \(f\)-ergodic strong Markov processes
• Fair Dynamic Routing in Large-Scale Heterogeneous-Server Systems
• Strong approximation for Markovian service networks
• Queue-and-idleness-ratio controls in many-server service systems
• Dynamic routing in large-scale service systems with heterogeneous servers
• On patient flow in hospitals: a data-based queueing-science perspective
• Service-level differentiation in many-server service systems via queue-ratio routing
• Ergodic diffusion control of multiclass multi-pool networks in the Halfin-Whitt regime
• Positive recurrence of piecewise Ornstein-Uhlenbeck processes and common quadratic Lyapunov functions
• Systems with large flexible server pools: instability of ``natural load balancing
• A diffusion model of scheduling control in queueing systems with many servers
• Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic
• State space collapse in many-server diffusion limits of parallel server systems
• Optimal control of parallel server systems with many servers in heavy traffic
• On dynamic scheduling of a parallel server system with complete resource pooling
• Second derivatives in convex analysis
• Ergodic control of multi-class \(\mathrm{M}/\mathrm{M}/N+\mathrm{M}\) queues in the Halfin-Whitt regime
• Stochastic networks
• Tightness of stationary distributions of a flexible-server system in the Halfin-Whitt asymptotic regime
• An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
• Simplified control problems for multiclass many-server queueing systems
• Infinite-horizon average optimality of the N-network in the Halfin-Whitt regime

Cited In (11)

• Ergodicity of a Lévy-driven SDE arising from multiclass many-server queues
• Time‐average stochastic control based on a singular local Lévy model for environmental project planning under habit formation
• Ergodic control of diffusions with compound Poisson jumps under a general structural hypothesis
• On System-Wide Safety Staffing of 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
• Control of parallel non-observable queues: asymptotic equivalence and optimality of periodic policies
• Optimal Control of Distributed Parallel Server Systems Under the Halfin and Whitt Regime
• Optimal control of Markov-modulated multiclass many-server queues
• On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime
• Uniform stability of some large-scale parallel server networks

This page was built for publication: Infinite horizon asymptotic average optimality for large-scale parallel server networks

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