Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-28T22:14:52.871Z Has data issue: false hasContentIssue false
  • English
  • Français

Cyclic queueing networks with subexponential service times

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  14 July 2016

H. Ayhan ,
Z. Palmowski  and
S. Schlegel
H. Ayhan*
Affiliation:
Georgia Institute of Technology
Z. Palmowski*
Affiliation:
University of Wrocław
S. Schlegel*
Affiliation:
University of Ulm
*
∗ Postal address: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, USA. Email address: [email protected]
∗∗ Postal address: Mathematical Institute, University of Wrocław, pl. Grunwaldzki 2/4, 50-384 Wrocław, Poland
∗∗∗ Postal address: Department of Biometry and Medical Documentation, University of Ulm, 89069 Ulm, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

For a K-stage cyclic queueing network with N customers and general service times, we provide bounds on the nth departure time from each stage. Furthermore, we analyze the asymptotic tail behavior of cycle times and waiting times given that at least one service-time distribution is subexponential.

Keywords

Cycle timeclosed networksubexponential asymptoticsHarris Markov chain

MSC classification

Primary: 60K25: Queueing theory 90B22: Queues and service 60K20: Applications of Markov renewal processes (reliability, queueing networks, etc.)
Type
Research Papers
Information
Journal of Applied Probability , Volume 41 , Issue 3 , September 2004 , pp. 791 - 801
Copyright
Copyright © Applied Probability Trust 2004 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Asmussen, S. (1987). Applied Probability and Queues. John Wiley, New York.Google Scholar
Ayhan, H., Palmowski, Z., and Schlegel, S. (2002). Subexponential asymptotics of cycle time in closed networks. Res. Rep. 024, EURANDOM.Google Scholar
Baccelli, F. and Brémaud, P. (1992). Elements of Queueing Theory. Springer, Berlin.Google Scholar
Baccelli, F., and Foss, S. (2004). Moments and tails in monotone-separable stochastic networks. Ann. Appl. Prob. 14, 612–650.Google Scholar
Baccelli, F., Foss, S., and Lelarge, M. (2004). Asymptotics of subexponential max plus networks: the stochastic event graph case. Queueing Systems 46, 75–96.10.1023/B:QUES.0000021142.51241.76Google Scholar
Baccelli, F., Foss, S., and Mairesse, J. (1996). Stationary ergodic Jackson networks: results and counter-examples. In Stochastic Networks: Theory and Applications, eds Kelly, F. P., Zachary, S. and Ziedins, I., Oxford University Press, pp. 281–307.Google Scholar
Baccelli, F., Schlegel, S., and Schmidt, V. (1999). Asymptotics of stochastic networks with subexponential service times. Queueing Systems 33, 205–232.10.1023/A:1019176129224Google Scholar
Baccelli, F. L., Cohen, G., Olsder, G. J., and Quadrat, J.-P. (1992). Synchronization and Linearity. An Algebra for Discrete Event Systems. John Wiley, Chichester.Google Scholar
Borovkov, A. A. (1984). Asymptotic Methods in Queueing Theory. John Wiley, New York.Google Scholar
Borovkov, A. A. (1986). Limit theorems for service networks I. J. Theory Prob. Appl. 31, 413–427.10.1137/1131056Google Scholar
Boxma, O. J. (1983). The cyclic queue with one general and one exponential server. Adv. Appl. Prob. 15, 857–873.10.2307/1427328Google Scholar
Boxma, O. J., and Donk, P. (1982). On response time and cycle time distribution in a two-stage cyclic queue. Performance Evaluation 2, 181–194.10.1016/0166-5316(82)90010-4Google Scholar
Boxma, O. J., Kelly, F. P., and Konheim, A. G. (1984). The product form for sojourn time distributions in cyclic exponential queues. J. Assoc. Comput. Mach. 31, 128–133.10.1145/2422.322419Google Scholar
Chistyakov, V. P. (1964). A theorem on sums of independent, positive random variables and its applications to branching processes. Theory Prob. Appl. 9, 640–648.10.1137/1109088Google Scholar
Chow, W. M. (1980). The cycle time distribution of exponential cyclic queues. J. Assoc. Comput. Mach. 27, 281–286.10.1145/322186.322193Google Scholar
Cline, D. B. H. (1986). Convolution tails, product tails and domains of attraction. Prob. Theory Relat. Fields 72, 529–557.10.1007/BF00344720Google Scholar
Daduna, H., and Szekli, R. (2004). On the correlation structure of closed queueing networks. Stoch. Models 20, 1–29.10.1081/STM-120028388Google Scholar
Embrechts, P., and Goldie, C. M. (1982). On convolution tails. Stoch. Process. Appl. 13, 263–278.10.1016/0304-4149(82)90013-8Google Scholar
Foss, S. (1991). Ergodicity of queueing networks. Siberian Math. J. 32, 184–203.Google Scholar
Foss, S., and Kalashnikov, V. (1991). Regeneration and renovation in queues. Queueing Systems 8, 211–224.10.1007/BF02412251Google Scholar
Gordon, W. J., and Newell, G. F. (1967). Closed queueing networks with exponential servers. Operat. Res. 15, 252–267.10.1287/opre.15.2.254Google Scholar
Huang, T., and Sigman, K. (1999). Steady-state asymptotics for tandem, split-match and other feedforward queues with heavy tailed service. Queueing Systems 33, 233–259.10.1023/A:1019128213295Google Scholar
Pitman, E. J. G. (1980). Subexponential distribution functions. J. Austral. Math. Soc. A 29, 337–347.Google Scholar
Schassberger, R., and Daduna, H. (1983). The time for a round trip in a cycle of exponential queues. J. Assoc. Comput. Mach. 30, 146–150.10.1145/322358.322369Google Scholar
Sigman, K. (1989). Notes on the stability of closed networks. J. Appl. Prob. 26, 678–682.10.2307/3214428Google Scholar