Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic

Abstract

A multiclass queueing system is considered, with heterogeneous service stations, each consisting of many servers with identical capabilities. An optimal control problem is formulated, where the control corresponds to scheduling and routing, and the cost is a cumulative discounted functional of the system's state. We examine two versions of the problem: ``nonpreemptive,'' where service is uninterruptible, and ``preemptive,'' where service to a customer can be interrupted and then resumed, possibly at a different station. We study the problem in the asymptotic heavy traffic regime proposed by Halfin and Whitt, in which the arrival rates and the number of servers at each station grow without bound. The two versions of the problem are not, in general, asymptotically equivalent in this regime, with the preemptive version showing an asymptotic behavior that is, in a sense, much simpler. Under appropriate assumptions on the structure of the system we show: (i) The value function for the preemptive problem converges to $V$, the value of a related diffusion control problem. (ii) The two versions of the problem are asymptotically equivalent, and in particular nonpreemptive policies can be constructed that asymptotically achieve the value $V$. The construction of these policies is based on a Hamilton--Jacobi--Bellman equation associated with $V$.

Published at http://dx.doi.org/10.1214/105051605000000601 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic
• Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
• A diffusion model of scheduling control in queueing systems with many servers

Cited by in corpus (10)

• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• A diffusion model of scheduling control in queueing systems with many servers
• Ergodic control of multi-class $M/M/N+M$ queues in the Halfin-Whitt regime
• Queueing systems with many servers: Null controllability in heavy traffic
• Scheduling parallel servers in the nondegenerate slowdown diffusion regime: Asymptotic optimality results
• On optimality gaps in the Halfin--Whitt regime
• Infinite horizon asymptotic average optimality for large-scale parallel server networks
• Ergodic Diffusion Control of Multiclass Multi-Pool Networks in the Halfin-Whitt Regime
• Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime
• Necessary condition for null controllability in many-server heavy traffic