On the improvement from scheduling a two-station queueing network in heavy traffic. (English) Zbl 0755.60075

Summary: For a two-station multiclass queueing network in heavy traffic, we assess the improvement from scheduling (job release and priority sequencing) that can occur relative to Poisson input and first-come first-served (FCFS) sequencing. In particular, simple upper bounds are derived on the optimal objective function value [found in the paper of the second author, Math. Oper. Res. 15, No. 2, 215-242 (1990; Zbl 0714.90042)] of a Brownian control problem that approximates (via J. M. Harrison’s model [Stochastic differential systems, stochastic control theory and applications, Proc. Workshop Minneapolis/Minn. 1986, IMA Vol. Math. Appl. 10, 147-186 (1988; Zbl 0658.60123)]) a two-station queueing network scheduling problem in heavy traffic. When the system is perfectly balanced, the Brownian analysis predicts that optimal scheduling will reduce the long run expected average number of customers in the network by at least a factor of four relative to the Poisson input, FCFS sequencing policy that achieves the same throughput rate. When the system is not perfectly balanced, the corresponding factor is slightly smaller than two.


60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI Link


[1] Baskett, F.; Chandy, K. M.; Muntz, R. R.; Palacios, F. G., Open, closed and mixed networks of queues with different classes of customers, J. Assoc. Comput. Mach., 22, 248-260 (1975) · Zbl 0313.68055
[2] Harrison, J. M., Brownian models of queueing networks with heterogeneous customer populations, (Fleming, W.; Lions, P. L., Stochastic Differential Systems, Stochastic Control Theory and Applications, IMA Volume 10 (1988), Springer-Verlag: Springer-Verlag New York), 147-186 · Zbl 0658.60123
[3] Kelly, F. P., Reversibility and Stochastic Networks (1979), John Wiley: John Wiley New York · Zbl 0422.60001
[4] Kushner, H. J.; Martins, L. F., Limit theorems for pathwise average cost per unit time problems for queues in heavy traffic, (Lefschetz Center for Dynamical Systems Report #91-2 (1991), Brown University) · Zbl 0806.60019
[5] Kushner, H. J.; Ramachandran, K. M., Optimal and approximately optimal control policies for queues in heavy traffic, SIAM J. Control Optim., 27, 1293-1318 (1989) · Zbl 0691.93068
[6] Martins, L. F.; Kushner, H. J., Routing and singular control for queueing networks in heavy traffic, SIAM J. Control Optim., 28, 1209-1233 (1990) · Zbl 0718.90029
[7] Wein, L. M., Optimal control of a two-station Brownian network, Math. Oper. Res., 15, 215-242 (1990) · Zbl 0714.90042
[8] Wein, L. M., Scheduling networks of queues: Heavy traffic analysis of a two-station network with controllable inputs, Oper. Res., 38, 1065-1078 (1991) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.