### Dynamic Scheduling of a Parallel Server System in Heavy Traffic with Complete Resource Pooling: Asymptotic Optimality of a Threshold Policy

**Steven L. Bell**

*(University of California, San Diego)*

**Ruth J. Williams**

*(University of California, San Diego)*

#### Abstract

We consider a parallel server queueing system consisting of a bank of buffers for holding incoming jobs and a bank of flexible servers for processing these jobs. Incoming jobs are classified into one of several different classes (or buffers). Jobs within a class are processed on a first-in-first-out basis, where the processing of a given job may be performed by any server from a given (class-dependent) subset of the bank of servers. The random service time of a job may depend on both its class and the server providing the service. Each job departs the system after receiving service from one server. The system manager seeks to minimize holding costs by dynamically scheduling waiting jobs to available servers. We consider a parameter regime in which the system satisfies both a heavy traffic and a complete resource pooling condition. Our cost function is an expected cumulative discounted cost of holding jobs in the system, where the (undiscounted) cost per unit time is a linear function of normalized (with heavy traffic scaling) queue length. In a prior work, the second author proposed a continuous review threshold control policy for use in such a parallel server system. This policy was advanced as an "interpretation" of the analytic solution to an associated Brownian control problem (formal heavy traffic diffusion approximation). In this paper we show that the policy proposed previously is asymptotically optimal in the heavy traffic limit and that the limiting cost is the same as the optimal cost in the Brownian control problem.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1044-1115

Publication Date: September 7, 2005

DOI: 10.1214/EJP.v10-281

#### References

- 1. B. Ata and S. Kumar.
Heavy traffic analysis of open processing networks with complete resource
pooling: asymptotic optimality of discrete review policies.
*Annals of Applied Probability*,**15**(2005), 331-391. Math. Review MR2115046 - 2. S. L. Bell.
*Dynamic Scheduling of a Parallel Server System in Heavy Traffic with Complete Resource Pooling: Asymptotic Optimality of a Threshold Policy.*Ph.D. dissertation, Department of Mathematics, University of California, San Diego, 2003. Math. Review number not available. -
3. S. L. Bell and R. J. Williams.
Dynamic scheduling of a system with two parallel servers
in heavy traffic with resource pooling:
asymptotic optimality of a threshold policy.
*Annals of Applied Probability*,**11**(2001), 608-649. Math. Review MR1865018 -
4. P. Billingsley.
*Convergence of Probability Measures.*John Wiley and Sons, New York, 1968. Math. Review MR0233396 -
5. M. Bramson. State space collapse with applications to heavy
traffic limits for multiclass queueing networks.
*Queueing Systems*,**30**(1998), 89-148. Math. Review MR1663763 -
6. M. Bramson and R. J. Williams.
Two workload properties for Brownian networks.
*Queueing Systems*,**45**(2003), 191-221. Math. Review MR2024178 - 7. A. Budhiraja and A. P. Ghosh,
A large deviations approach to asymptotically optimal control of
crisscross network in heavy traffic.
*Annals of Applied Probability,***15**(2005), 1887-1935. Math. Review number not available. - 8. P. B. Chevalier and L. Wein. Scheduling networks
of queues: heavy traffic analysis of a multistation closed network.
*Operations Research,***41**(1993), 743-758. Math. Review number not available. - 9. K. L. Chung and R. J. Williams.
*Introduction to Stochastic Integration*. 2nd edition, Birkhäuser, Boston, 1990. Math. Review of 1st Edition MR0711774 -
10. S. N. Ethier and T. G. Kurtz.
*Markov Processes: Characterization and Convergence.*Wiley, New York, 1986. Math. Review MR0838085 -
11. J. M. Harrison.
*Brownian Motion and Stochastic Flow Systems.*John Wiley and Sons, New York, 1985. Math. Review MR0798279 -
12. J. M. Harrison. Brownian models of queueing networks with
heterogeneous customer populations. In
*Stochastic Differential Systems, Stochastic Control Theory and Their Applications, IMA Volume 10*, W. Fleming and P. L. Lions (eds.), Springer Verlag, New York, 1988, pp. 147-186. Math. Review MR0934722 - 13. J. M. Harrison.
Balanced fluid models of multiclass queueing networks: a
heavy traffic conjecture.
In
*Stochastic Networks*, F. P. Kelly and R. J. Williams (eds.), Springer-Verlag, 1995, pp. 1-20. Math. Review MR1381003 - 14. J. M. Harrison. The BIGSTEP approach to flow management in
stochastic processing networks. In
*Stochastic Networks: Theory and Applications,*F. P. Kelly, S. Zachary and I. Ziedins (eds.), Oxford University Press, 1996, pp. 57-90. Math. Review number not available. -
15. J. M. Harrison. Heavy traffic analysis of a system with parallel servers:
asymptotic optimality of discrete-review policies.
*Annals of Applied Probability*,**8**(1998), 822-848. Math. Review MR1627791 -
16. J. M. Harrison.
Brownian models of open processing networks:
canonical representation of workload.
*Annals of Applied Probability*,**10**(2000), 75-103. Correction:**13**(2003), 390-393. Math. Review MR1765204 - 17. J. M. Harrison. A broader view of Brownian networks.
*Annals of Applied Probability*,**13**(2003), 1119-1150. Math. Review MR1994047 -
18. J. M. Harrison and M. J. López. Heavy traffic resource pooling
in parallel-server systems.
*Queueing Systems,***33**(1999), 339-368. Math. Review MR1742575 -
19. J. M. Harrison and J. A. Van Mieghem. Dynamic control of Brownian
networks: state space collapse and equivalent workload formulations.
*Annals of Applied Probability,***7**(1997), 747-771. Math. Review MR1459269 - 20. J. M. Harrison and L. Wein. Scheduling networks of queues:
heavy traffic analysis of a simple open network.
*Queueing Systems,***5**(1989), 265-280. Math. Review MR1030470 - 21. J. M. Harrison and L. Wein. Scheduling networks of queues:
heavy traffic analysis of a two-station closed network.
*Operations Research,***38**(1990), 1052-1064. Math. Review MR1095959 -
22. D. L. Iglehart and W. Whitt.
The equivalence of functional central limit theorems for
counting processes and associated partial sums.
*Ann. Math. Statist.,***42**(1971), 1372-1378. Math. Review MR0310941 -
23. W. C. Jordan and C. Graves. Principles on the benefits of manufacturing
process flexibility.
*Management Science,***41**(1995), 577-594. Math. Review number not available. - 24. F. P. Kelly and C. N. Laws. Dynamic routing in open queueing
networks:
Brownian models, cut constraints and resource pooling.
*Queueing Systems,***13**(1993), 47-86. Math. Review MR1218844 - 25. H. J. Kushner and Y. N. Chen. Optimal
control of assignment of jobs to processors
under heavy traffic.
*Stochastics and Stochastics Rep.,*(2000), no. 3-4, pp. 177-228. Math. Review MR1746180**68** - 26. H. J. Kushner and P. Dupuis.
*Numerical Methods for Stochastic Control Problems in Continuous Time.*Springer-Verlag, New York, 1992. Math. Review MR1217486 - 27. H. J. Kushner and L. F. Martins.
Numerical methods
for stochastic singular control problems.
*SIAM J. Control and Optimization***29**(1991), 1443-1475. Math. Review MR1132190 - 28. C. N. Laws.
*Dynamic Routing in Queueing Networks.*Ph.D. dissertation, Statistical Laboratory, University of Cambridge, U.K., 1990. Math. Review number not available. - 29. C. N. Laws.
Resource pooling in queueing networks with dynamic
routing.
*Advances in Applied Probability,***24**(1992), 699-726. Math. Review MR1174386 - 30. C. N. Laws and G. M. Louth. Dynamic scheduling of a four-station
queueing network.
*Probab. Engrg. Inform. Sci.,***4**(1990), 131-156. Math. Review number not available. -
31. A. Mandelbaum and A. L. Stolyar.
Scheduling flexible servers with convex delay costs:
heavy-traffic optimality of the generalized c-mu-rule.
*Operations Research*,**52**(2004), 836-855. Math. Review MR2104141 -
32. S. P. Meyn. Dynamic safety-stocks for asymptotic optimality in stochastic networks
.
*Queueing Systems,***50**(2005), 255-297. Math. Review number not available. - 33. T. Osogami, M. Harchol-Balter, A. Scheller-Wolf, and L. Zhang.
Exploring threshold-based policies for load sharing.
*Proceedings of 42nd Annual Allerton Conference on Communication, Control and Computing,*University of Illinois, Urbana-Champaign, October 2004. Math. Review number not available. - 34. W. P. Peterson. A heavy traffic limit theorem for networks
of queues with multiple customer types.
*Mathematics of Operations Research,***16**(1991), 90-118. Math. Review MR1106792 - 35. M. Squillante, C. H. Xia, D. Yao, and L. Zhang.
Threshold-based priority policies for parallel-server systems with affinity
scheduling.
*Proc. IEEE American Control Conference*(2001), 2992-2999. Math. Review number not available. -
36. A. L. Stolyar.
Maxweight scheduling in a generalized switch: state space
collapse and workload minimization in heavy traffic.
*Annals of Applied Probability*,**14**(2004), 1-53. Math. Review MR2023015 -
37. Y. C. Teh.
*Threshold Routing Strategies for Queueing Networks.*D. Phil. thesis, University of Oxford, 1999. Math. Review number not available. -
38. Y. C. Teh and A. R. Ward.
Critical thresholds for dynamic routing in queueing networks.
*Queueing Systems*,**42**(2002), 297-316. Math. Review MR1935144 -
39. L. Wein. Scheduling networks of queues: heavy traffic analysis
of a two-station network with controllable inputs.
*Operations Research,***38**(1990), 1065-1078. Math. Review MR1095960 - 40. R. J. Williams.
An invariance principle for semimartingale reflecting Brownian motions
in an orthant.
*Queueing Systems*,**30**(1998), 5-25. Math. Review MR1663755 - 41. R. J. Williams. Diffusion approximations
for open multiclass queueing networks: sufficient conditions
involving state space collapse.
*Queueing Systems*,**30**(1998), 27-88. Math. Review MR1663759 - 42. R. J. Williams. On dynamic scheduling of a
parallel server system with complete resource pooling.
In
*Analysis of Communication Networks: Call Centres, Traffic and Performance,*D. R. McDonald and S. R. E. Turner (eds.), American Mathematical Society, Providence, RI, 2000, 49-71. Math. Review MR1788708

This work is licensed under a Creative Commons Attribution 3.0 License.