Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 10 (2005) > Paper 33 open journal systems 


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: PDF

Pages: 1044-1115

Published on: September 7, 2005
Bibliography
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., 68 (2000), no. 3-4, pp. 177-228. Math. Review MR1746180

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















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489