Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies
Open Access
- 1 August 1998
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 8 (3), 822-848
- https://doi.org/10.1214/aoap/1028903452
Abstract
This paper is concerned with dynamic scheduling in a queueing system that has two independent Poisson input streams, two servers, deterministic service times and linear holding costs. One server can process both classes of incoming jobs, but the other can process only one class, and the service time for the shared job class is different depending on which server is involved. A bound on system performance is developed in terms of a single pooled resource, or super-server, whose capabilities combine those of the original two servers. Thereafter, attention is focused on the heavy traffic regime, where the combined capacity of the two servers is approximately equal to the total input rate. We construct a discrete-review control policy and show that if its parameters are chosen correctly as one approaches the heavy traffic limit, then its cost performance approaches the bound associated with a single pooled resource. Thus the discrete-review policy is proved to be asymptotically optimal in the heavy traffic limit. Although resource pooling in heavy traffic has been observed to occur in other network scheduling problems, there have been very few studies that rigorously proved the pooling phenomenon, or that proved the asymptotic optimality of a specific policy. Our discrete-review policy is obtained by applying a general method, called the BIGSTEP method in an earlier paper, to the parallel-server model.Keywords
This publication has 13 references indexed in Scilit:
- Some diffusion approximations with state space collapsePublished by Springer Nature ,2005
- Dynamic control of Brownian networks: state space collapse and equivalent workload formulationsThe Annals of Applied Probability, 1997
- Dynamic Scheduling with Convex Delay Costs: The Generalized $c|mu$ RuleThe Annals of Applied Probability, 1995
- Dynamic routing in open queueing networks: Brownian models, cut constraints and resource poolingQueueing Systems, 1993
- A network of priority queues in heavy traffic: One bottleneck stationQueueing Systems, 1990
- Scheduling networks of queues: Heavy traffic analysis of a simple open networkQueueing Systems, 1989
- Brownian Models of Queueing Networks with Heterogeneous Customer PopulationsPublished by Springer Nature ,1988
- Open Queueing Networks in Heavy TrafficMathematics of Operations Research, 1984
- A Basic Dynamic Routing Problem and DiffusionIEEE Transactions on Communications, 1978
- The supremum distribution of a Lévy process with no negative jumpsAdvances in Applied Probability, 1977