Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic
Open Access
- 1 November 2005
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 15 (4), 2606-2650
- https://doi.org/10.1214/105051605000000601
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.Keywords
This publication has 12 references indexed in Scilit:
- Heavy traffic analysis of open processing networks with complete resource pooling: Asymptotic optimality of discrete review policiesThe Annals of Applied Probability, 2005
- A diffusion model of scheduling control in queueing systems with many serversThe Annals of Applied Probability, 2005
- Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-RuleOperations Research, 2004
- Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy trafficThe Annals of Applied Probability, 2004
- Telephone Call Centers: Tutorial, Review, and Research ProspectsManufacturing & Service Operations Management, 2003
- Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policyThe Annals of Applied Probability, 2001
- On dynamic scheduling of a parallel server system with complete resource poolingPublished by American Mathematical Society (AMS) ,2000
- Brownian models of open processing networks: canonical representation of workloadThe Annals of Applied Probability, 2000
- Markov ProcessesWiley Series in Probability and Statistics, 1986
- Heavy-Traffic Limits for Queues with Many Exponential ServersOperations Research, 1981