Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic

Abstract

We consider the problem of scheduling a queueing system in which many statistically identical servers cater to several classes of impatient customers. Service times and impatience clocks are exponential while arrival processes are renewal. Our cost is an expected cumulative discounted function, linear or nonlinear, of appropriately normalized performance measures. As a special case, the cost per unit time can be a function of the number of customers waiting to be served in each class, the number actually being served, the abandonment rate, the delay experienced by customers, the number of idling servers, as well as certain combinations thereof. We study the system in an asymptotic heavy-traffic regime where the number of servers n and the offered load r are simultaneously scaled up and carefully balanced: n\approx r+β\sqrtr for some scalar β. This yields an operation that enjoys the benefits of both heavy traffic (high server utilization) and light traffic (high service levels.)

Cited by in corpus (19)

• Scheduling control for queueing systems with many servers: asymptotic optimality in heavy traffic
• A diffusion model of scheduling control in queueing systems with many servers
• Central limit theorem for a many-server queue with random service rates
• 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
• On optimality gaps in the Halfin--Whitt regime
• Infinite Horizon Average Optimality of the N-network Queueing Model in the Halfin-Whitt Regime
• On uniform exponential ergodicity of Markovian multiclass many-server queues in the Halfin-Whitt regime
• Economies-of-scale in resource sharing systems: tutorial and partial review of the QED heavy-traffic regime
• Latency-Redundancy Tradeoff in Distributed Read-Write Systems
• Admission Control for Double-ended Queues
• Robust bounds and optimization at the large deviations scale for queueing models via Rényi divergence
• Multi-component Matching Queues in Heavy Traffic
• Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment
• Efficient routing in heavy traffic under partial sampling of service times
• Necessary condition for null controllability in many-server heavy traffic
• Asymptotic dimensioning of stochastic service systems
• An Overview for Markov Decision Processes in Queues and Networks
• Risk-sensitive control for the multi-class many server queue in the moderate deviation regime