Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete-review policies. (English) Zbl 0938.60094

The paper deals with dynamic scheduling in a queueing system M/2/D/2 with linear holding costs. A discrete-review control policy is constructed and its asymptotical optimality in the heavy traffic is proved. A main tool for the above discussion is the so-called BIGSTEP method.


60K25 Queueing theory (aspects of probability theory)
90B15 Stochastic network models in operations research
90B22 Queues and service in operations research
Full Text: DOI


[1] Billingsley, P. (1968). Convergence of Probability Measures. Wiley, New York. · Zbl 0172.21201
[2] Chevalier, P. B. and Wein, L. M. (1993). Scheduling networks of queues: heavy traffic analysis of a multistation closed network. Oper. Res. 41 743-758. · Zbl 0782.90037
[3] Foschini, G. J. (1977). On heavy traffic diffusion analysis and dy namic routing in packet switched networks. In Computer Performance (K. M. Chandy and M. Reiser, eds.) 499- 514. North-Holland, Amsterdam.
[4] Foschini, G. J. and Salz, J. (1978). A basic dy namic routing problem and diffusion. IEEE Trans. Comm. COM-26 320-327. · Zbl 0383.90047
[5] Harrison, J. M. (1977). The supremum distribution of a Levy process with no negative jumps. Adv. in Appl. Probab. 9 417-422. JSTOR: · Zbl 0366.60056
[6] Harrison, J. M. (1985). Brownian Motion and Stochastic Flow Sy stems. Wiley, New York. · Zbl 0659.60112
[7] Harrison, J. M. (1988). Brownian models of queueing networks with heterogeneous customer populations. In Stochastic Differential Sy stems, Stochastic Control Theory and Applications (W. Fleming and P.-L. Lions, eds.) 147-186. Springer, New York. · Zbl 0658.60123
[8] Harrison, J. M. (1996). 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.) 57-90. Oxford Univ. Press. · Zbl 0860.60068
[9] Harrison, J. M. and Wein, L. M. (1989). Scheduling networks of queues: heavy traffic analysis of a simple open network. Queueing Sy stems Theory Appl. 5 265-280. · Zbl 0684.90034
[10] Harrison, J. M. and Wein, L. M. (1990). Scheduling networks of queues: heavy traffic analysis of a two-station closed network. Oper. Res. 38 1052-1064. JSTOR: · Zbl 0723.90026
[11] Harrison, J. M. and Van Mieghem, J. A. (1997). Dy namic control of Brownian networks: state space collapse and equivalent workload formulations. Ann. Appl. Probab. 7 744- 771. · Zbl 0885.60080
[12] Kelly, F. P. and Laws, C. N. (1993). Dy namic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Sy stems Theory Appl. 13 47-86. · Zbl 0772.60068
[13] Reiman, M. I. (1983). Some diffusion approximations with state space collapse. Proceedings of the International Seminar on Modelling and Performance Evaluation Methodology, Lecture Notes in Control and Inform. Sci. 60 209-240. Springer, Berlin. · Zbl 0545.60089
[14] Reiman, M. I. (1984). Open queueing networks in heavy traffic. Math. Oper. Res. 9 441-458. JSTOR: · Zbl 0549.90043
[15] Reiman, M. I. and Simon, B. (1990). A network of priority queues in heavy traffic: one bottleneck station. Queueing Sy stems Theory Appl. 6 33-58. · Zbl 0818.60081
[16] Van Mieghem, J. (1995). Dy namic scheduling with convex delay costs: the generalized c\mu rule. Ann. Appl. Probab. 5 809-833. · Zbl 0843.90047
[17] Wein, L. M. (1990). Brownian networks with discretionary routing. Oper. Res. 38 1065-1078. JSTOR: · Zbl 0724.90025
[18] Wein, L. M. (1991). Scheduling networks of queues: heavy traffic analysis of a two-station network with controllable inputs. Oper. Res. 39 322-340. JSTOR: · Zbl 0724.90025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.