zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Brownian models of multiclass queueing networks: Current status and open problems. (English) Zbl 0781.60090
The problem of heavy traffic approximation by reflected Brownian motion (BM) for open queueing network with $D$ nodes and $C$ customer classes is surveyed. The network has Markovian routing, and customers are assumed to switch among classes in Markovian fashion also. It is assumed that external input processes can be correlated and obey some functional central limit theorem with limiting $C$-dimensional BM with zero drift. The same is right for cumulative service capacity process, too (with $D$- dimensional limiting BM). The relation between BM and heavy traffic theory is discussed. Continuous time workload, queue-size and some other basic processes are introduced for each customer type and the whole network. A natural scaling of time and space is considered. The main scaling factor is the vector of differences between long-time average service rates and traffic intensities for all nodes. Then the Brownian model is defined that approximates scaled system of the mentioned network processes. Heavy traffic convergence is considered. Two numerical examples are presented where complete sojourn time distributions are estimated.

60K25Queueing theory
90B22Queues and service (optimization)
60J65Brownian motion
Full Text: DOI
[1] V. Benes,General Stochastic Processes in the Theory of Queues (Addison-Wesley, Reading, MA, 1963). · Zbl 0125.09802
[2] H. Chen and A. Mandelbaum, Stochastic discrete flow networks: Diffusion approximations and bottlenecks, Ann. Prob. 19(1991) 1463-1519. · Zbl 0757.60094 · doi:10.1214/aop/1176990220
[3] H. Chen and W. Whitt, Diffusion approximations for open queueing networks with server interruptions, submitted. · Zbl 0783.60088
[4] J.G. Dai and J.M. Harrison, Reflected Brownian motion in an orthant: Numerical methods for steady-state analysis, Ann. Appl. Prob. 2 (1992) 65-86. · Zbl 0786.60107 · doi:10.1214/aoap/1177005771
[5] P.W. Glynn, Diffusion approximations, in:Handbook on OR and MS, Vol. 2, eds. D.P. Heyman and M.J. Sobel (Elsevier Science/North-Holland, 1990) pp. l45-198.
[6] B.S. Greenberg, Queueing systems with returning customers and the order of tandem queues, Ph.D. Dissertation, University of California, Berkeley (1986).
[7] S. Halfin and W. Whitt, Heavy traffic limits for queues with many exponential servers, Oper. Res. 29 (1981) 567-588. · Zbl 0455.60079 · doi:10.1287/opre.29.3.567
[8] J.M. Harrison, The diffusion approximation for tandem queues in heavy traffic, Adv. Appl. Prob. 10 (1978) 886-905. · Zbl 0387.60090 · doi:10.2307/1426665
[9] J.M. Harrison,Brownian Motion and Stochastic Flow Systems (Wiley, New York, 1985). · Zbl 0659.60112
[10] J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, in:Stochastic Differential Systems, Stochastic Control Theory and Their Applications, eds. W. Fleming and P.L. Lions, Vol. 10 in the IMA Series on Mathematics and its Applications (Springer, New York, 1988) pp. 147-186.
[11] J.M. Harrison and V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Systems 6 (1990) 1-32. · Zbl 0702.60082 · doi:10.1007/BF02411463
[12] J.M. Harrison and M.I. Reiman, Reflected Brownian motion on an orthant, Ann. Prob. 9 (1981) 302-308. · Zbl 0462.60073 · doi:10.1214/aop/1176994471
[13] J.M. Harrison and R.J. Williams, Multidimensional reflected Brownian motions having exponential stationary distributions, Ann. Prob. 15 (1987) 115-137. · Zbl 0615.60072 · doi:10.1214/aop/1176992259
[14] J.M. Harrison and R.J. Williams, Brownian models of open queueing networks with homogeneous customer populations, Stochastics 22 (1987) 77-115. · Zbl 0632.60095
[15] J.M. Harrison and R.J. Williams, Brownian models of feedforward queueing networks: Quasireversibility and product-form solution, Ann. Appl. Prob. 2 (1992) 263-293. · Zbl 0753.60071 · doi:10.1214/aoap/1177005704
[16] D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic, I and II, Adv. Appl. Prob. 2 (1970) 150-177 and 355-364. · Zbl 0218.60098 · doi:10.2307/3518347
[17] J.R. Jackson, Networks of waiting lines, Oper. Res. 5 (1957) 518-521. · doi:10.1287/opre.5.4.518
[18] J.R. Jackson, Jobshop-like queueing systems, Manag. Sci. 10 (1963) 131-142. · doi:10.1287/mnsc.10.1.131
[19] D.P. Johnson, Diffusion approximations for optimal filtering of jump processes and for queueing networks, Ph.D. Dissertation, University of Wisconsin, Madison (1983).
[20] O. Kella and W. Whitt, Diffusion approximations for queues with server vacations, Adv. Appl. Prob. 22 (1990) 706-729. · Zbl 0713.60101 · doi:10.2307/1427465
[21] F.P. Kelly,Reversibility and Stochastic Networks (Wiley, New York, 1979).
[22] J.F.C. Kingman, The heavy traffic approximation in the theory of queues, in:Congestion Theory, eds. W.L. Smith and W.E. Wilkinson (The University of North Carolina Press, Chapel Hill, 1965) pp. 137-159. · Zbl 0189.51604
[23] P.R. Kumar, Re-entrant lines, Queueing systems 13 (1993), this issue.
[24] W.P. Peterson, Diffusion approximations for networks of queues with multiple customer types, Math. Oper. Res. 16 (1991) 90-118. · Zbl 0727.60114 · doi:10.1287/moor.16.1.90
[25] M.T. Pich, Brownian models of open queueing networks with general station capabilities, Ph.D. Dissertation, Stanford University (1992).
[26] M.I. Reiman, The heavy traffic diffusion approximation for sojourn times in Jackson networks, in:Applied Probability-Computer Science: The Interface, Vol. 2, eds. R.L. Disney and T. Ott (Birkhäuser, Boston, 1982) pp. 409-422.
[27] M.I. Reiman, Open queueing networks in heavy traffic, Math. Oper. Res. 9 (1984) 441-458. · Zbl 0549.90043 · doi:10.1287/moor.9.3.441
[28] M.I. Reiman, A multiclass feedback queue in heavy traffic, Adv. Appl. Prob. 20 (1988) 179-207. · Zbl 0647.60100 · doi:10.2307/1427275
[29] M.I. Reiman and R. Williams, A boundary property of semimartingale reflecting Brownian motions, Prob. Theory Rel. Fields 77 (1988) 87-97. · Zbl 0617.60081 · doi:10.1007/BF01848132
[30] R. Suri and S. Treville, Full speed ahead, OR/MS Today (June 1991) 34-42.
[31] L. Taylor and R. Williams, Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant, Prob. Theory Rel. Fields, to appear. · Zbl 0794.60079
[32] W. Whitt, Heavy traffic theorems for queues: A survey, in:Mathematical Methods in Queueing Theory, ed. A.B. Clark (Springer, Berlin, 1974). · Zbl 0295.60081
[33] W. Whitt, Refining diffusion approximations for queues, Oper. Res. Lett. 1 (1982) 165-169. · Zbl 0538.90025 · doi:10.1016/0167-6377(82)90033-5
[34] W. Whitt, The queueing network analyzer, Bell Sys. Tech. J. 62 (1983) 2779-2185.
[35] W. Whitt, Large fluctuations in a deterministic multiclass network of queues, Manag. Sci. (1993), to appear. · Zbl 0783.60090
[36] R. Williams, Reflected Brownian motion with skew symmetric data in a polyhedral domain, Prob. Theory Rel. Fields 75 (1987) 459-485. · Zbl 0608.60074 · doi:10.1007/BF00320328