zbMATH — the first resource for mathematics

Towards better multi-class parametric-decomposition approximations for open queueing networks. (English) Zbl 0788.60116
Summary: Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is \(\Sigma(GI_ i/GI_ i)/1\) with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric- decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by G. R. Bitran and D. Tirupati [Manage. Sci. 34, No. 1, 75-100 (1988; Zbl 0636.60101)]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations.

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
90B15 Stochastic network models in operations research
Full Text: DOI
[1] S.L. Albin, Approximating a point process by a renewal process, II: Superposition arrival processes to queues, Oper. Res. 32 (1984) 1133–1162. · Zbl 0547.90034 · doi:10.1287/opre.32.5.1133
[2] S.L. Albin, Delays for customers from different arrival streams to a queue, Manag. Sci. 32 (1986) 329–340. · Zbl 0613.60092 · doi:10.1287/mnsc.32.3.329
[3] S.L. Albin and S. Kai, Approximation for the departure process of a queue in a network, Nav. Res. Log. Qtrly. 33 (1986) 129–143. · Zbl 0601.60097 · doi:10.1002/nav.3800330112
[4] P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968). · Zbl 0172.21201
[5] G.R. Bitran and D. Tirupati, Multiproduct queueing networks with deterministic routing: Decomposition approach and the notion of interference, Manag. Sci. 34 (1988) 75–100. · Zbl 0636.60101 · doi:10.1287/mnsc.34.1.75
[6] J.A. Buzacott and J.G. Shanthikumar, On approximate queueing models of dynamic job shops, Manag. Sci. 31 (1985) 347–366. · doi:10.1287/mnsc.31.7.870
[7] K.M. Chandy and C.H. Sauer, Approximate methods for analyzing queueing network models of computer systems, Comp. Surveys 10 (1978) 281–317. · Zbl 0385.68039 · doi:10.1145/356733.356737
[8] J.G. Dai, V. Nguyen and M.I. Reiman, Sequential bottleneck decomposition: An approximation method for open queueing networks, Oper. Res., to appear. · Zbl 0802.90046
[9] K.W. Fendick, V.R. Saksena and W. Whitt, Dependence in packet queues, IEEE Trans. Commun. COM-37 (1989) 1173–1183. · doi:10.1109/26.46511
[10] K.W. Fendick, V.R. Saksena and W. Whitt, Investigating dependence in packet queues with the index of dispersion for work, IEEE Trans. Commun. COM-39 (1991) 1231–1244. · doi:10.1109/26.134013
[11] W. Fischer and D. Stanford, Approximations for the per-class waiting time and interdeparture time in the \(\sigma\) i GI i /GI i /1 queue, Siemens, München (1989). · Zbl 0671.60086
[12] E. Gelenbe and I. Mitrani,Analysis and Synthesis of Computer Systems (Academic Press, New York, 1980). · Zbl 0484.68026
[13] J.M. Harrison and V. Nguyen, The QNET method for two-moment analysis of open queueing networks, Queueing Syst. 6 (1990) 1–32. · Zbl 0702.60082 · doi:10.1007/BF02411463
[14] J.M. Harrison and V. Nguyen, Brownian models of multiclass queueing networks: Current status and open problems, Queueing Syst. 13 (1993) 5–40. · Zbl 0781.60090 · doi:10.1007/BF01158927
[15] J.M. Holtzman, Mean delays of individual streams into a queue: The \(\sigma\)G i /M/1 queue,Applied Probability-Computer Science: The Interface, eds. R.L. Disney and T.J. Ott (Birkhäuser, Boston, 1982) pp. 417–430. · Zbl 0642.68052
[16] D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic, I, Adv. Appl. Prob. 2 (1970) 150–177. · Zbl 0218.60098 · doi:10.2307/3518347
[17] D.L. Iglehart and W. Whitt, Multiple channel queues in heavy traffic, II: Sequences, networks and batches, Adv. Appl. Prob. 2 (1970) 355–369. · Zbl 0206.22503 · doi:10.2307/1426324
[18] L. Kleinrock,Communication Nets (McGraw-Hill, New York, 1964). · Zbl 0274.90012
[19] W. Kraemer and M. Langenbach-Belz, Approximate formulae for the delay in the queueing systemGI/G/1,Proc. 8th Int. Teletraffic Congress, Melbourne (1976).
[20] P.J. Kuehn, Approximate analysis of general queueing networks by decomposition, IEEE Trans. Commun. COM-27 (1979) 113–126. · Zbl 0392.60070 · doi:10.1109/TCOM.1979.1094270
[21] B. Pourbabai and D. Sonderman, Approximation of departure process from aG/M/1/0 queueing system, Oper. Res. Lett. 4 (1986) 201–205. · Zbl 0585.60092 · doi:10.1016/0167-6377(86)90002-7
[22] M.I. Reiman, Asymptotically exact decomposition approximations for open queueing networks, Oper. Res. Lett. 9 (1990) 363–370. · Zbl 0711.60093 · doi:10.1016/0167-6377(90)90055-A
[23] M. Reiser and H. Kobayashi, Accuracy of the diffusion approximation for some queueing systems, IBM J. Res. Dev. 18 (1974) 110–124. · Zbl 0275.68014 · doi:10.1147/rd.182.0110
[24] M. Segal and W. Whitt, A queueing network analyser for manufacturing,Teletraffic Science for New Cost-Effective Systems, Networks and Services, ITC-12, ed. M. Bonatti (Elsevier Science, Amsterdam, 1989) pp. 1146–1152.
[25] K.C. Sevcik, A.I. Levy, S.K. Tripathi and J.L. Zahorjan, Improving approximations of aggregated queueing network subsystems,Computer Performance, eds. K.M. Chandy and M. Reiser (North-Holland, Amsterdam, 1977) pp. 1–22.
[26] J.G. Shanthikumar and J.A. Buzacott, Open queueing network models of dynamic job shops, Int. J. Prod. Res. 19 (1981) 255–266. · doi:10.1080/00207548108956652
[27] D.A. Stanford and W. Fischer, The interdeparture-time distribution for each class in the \(\sigma\)M i /G i /1 queue, Queueing Syst. 4 (1989) 177–190. · Zbl 0671.60086 · doi:10.1007/BF02100265
[28] D.A. Stanford and W. Fischer, Characterizing interdeparture times for bursty input streams in the queue with pooled renewal arrivals, Stoch. Mod. 7 (1991) 311–320. · Zbl 0731.60089 · doi:10.1080/15326349108807191
[29] S. Suresh and W. Whitt, The heavy-traffic bottleneck phenomenon in open queueing networks, Oper. Res. Lett. 9 (1990) 355–362. · Zbl 0709.60562 · doi:10.1016/0167-6377(90)90054-9
[30] W. Whitt, Some useful functions for functional limit theorems, Math. Oper. Res. 5 (1980) 67–85. · Zbl 0428.60010 · doi:10.1287/moor.5.1.67
[31] W. Whitt, Approximating a point process by a renewal process, I: Two basic methods, Oper. Res. 30 (1982) 125–147. · Zbl 0481.90025 · doi:10.1287/opre.30.1.125
[32] W. Whitt, The queueing network analyzer, Bell Syst. Tech. J. 62 (1983) 2779–2815.
[33] W. Whitt, Approximations for departure processes and queues in series, Nav. Res. Log. Qtrly. 31 (1984) 499–521. · Zbl 0563.60094 · doi:10.1002/nav.3800310402
[34] W. Whitt, Approximations for theGI/G/m queue, AT & T Bell Laboratories, Murray Hill, NJ (1985).
[35] W. Whitt, Approximations for single-class departure processes from multi-class queues, AT&T Bell Laboratories, Murray Hill, NJ (1987).
[36] W. Whitt, A light-traffic approximation for single-class departure processes from multi-class queues, Manage. Sci. 34 (1988) 1333–1346. · Zbl 0682.60082 · doi:10.1287/mnsc.34.11.1333
[37] W. Whitt, Large fluctuations in a deterministic multiclass network of queues, Manag. Sci. 39 (1993), to appear. · Zbl 0783.60090
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.