Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-14T16:58:57.333Z Has data issue: false hasContentIssue false
  • English
  • Français

Queueing networks with instantaneous movements: a unified approach by quasi-reversibility

Part of:Special processesMarkov processes

Published online by Cambridge University Press:  01 July 2016

Xiuli Chao and
Masakiyo Miyazawa
Xiuli Chao*
Affiliation:
New Jersey Institute of Thechnology
Masakiyo Miyazawa*
Affiliation:
Science University of Tokyo
*
∗ Postal address: New Jersey Institute of Technology, Newark, NJ 07102, USA.
∗∗ Postal address: Science University of Tokyo Noda, Chiba 278, Japan.
Get accessRights & Permissions [Opens in a new window]

Abstract

In this paper we extend the notion of quasi-reversibility and apply it to the study of queueing networks with instantaneous movements and signals. The signals treated here are considerably more general than those in the existing literature. The approach not only provides a unified view for queueing networks with tractable stationary distributions, it also enables us to find several new classes of product form queueing networks, including networks with positive and negative signals that instantly add or remove customers from a sequence of nodes, networks with batch arrivals, batch services and assembly-transfer features, and models with concurrent batch additions and batch deletions along a fixed or a random route of the network.

Keywords

Networks of queuespositive and negative signalsquasi-reversibilitycouplingdelayed and non-delayed signalsproduct form solutionstochastic bound

MSC classification

Primary:60K25: Queueing theory
Secondary:60J27: Continuous-time Markov processes on discrete state spaces

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 32 , Issue 1 , March 2000, pp. 284 - 313
Copyright
Copyright © Applied Probability Trust 2000 

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.)

Article purchase

Temporarily unavailable

References

Boucherie, R. J. and van Dijk, N. M. (1994). Local balances in queueing networks with positive and negative customers. Ann. Operat. Res. 48, 463–492.CrossRefGoogle Scholar
Chao, X. (1994). A note on queueing networks with signals and random triggering times. Probability in the Engineering and Informational Sciences, 8, 213–219.CrossRefGoogle Scholar
Chao, X. (1995). Networks of queues with customers, signals and arbitrary service time distributions. Operat. Res. 43, 537–544.CrossRefGoogle Scholar
Chao, X. and Miyazawa, M. (1998). On quasi-reversibility and local balance: an alternative derivation of product form results. Operat. Res. 46, 927–933. A probabilistic decomposition approach to quasi-reversibility and its applications in coupling of queues, preprint.CrossRefGoogle Scholar
Chao, X. and Pinedo, M. (1993). On generalized networks of queues with positive and negative arrivals. Prob. Eng. Inf. Sci. 7, 301–334.CrossRefGoogle Scholar
Chao, X. and Pinedo, M. (1995). Networks of queues with batch services, signals, and product form solutions. Operat. Res. Lett. 17, 237–242.CrossRefGoogle Scholar
Chao, X., Miyazawa, M., Serfozo, R. and Takada, H. (1998). Markov network processes with product form stationary distributions. Queueing Systems 28, 377–403.CrossRefGoogle Scholar
Chao, X., Miyazawa, M. and Pinedo, M. (1999). Queueing Networks: Customers, Signals, and Product Form Solutions. John Wiley, Chichester, UK.Google Scholar
Dembo, A. and Zeitouni, O. (1993). Large Deviation Techniques and Applications. Jones and Bartlett, Boston, MA.Google Scholar
Gelenbe, E. (1991). Product-form queueing networks with negative and positive customers. J. Appl. Prob. 28, 656–663.CrossRefGoogle Scholar
Gelenbe, E. (1993). G-networks with triggered customer movement. J. Appl. Prob. 30, 742–748.CrossRefGoogle Scholar
Henderson, W. and Taylor, P. G. (1990) Product form in networks of queues with batch arrivals and batch services, Queueing Systems 6, 71–88.CrossRefGoogle Scholar
Henderson, W. (1993). Queueing networks with negative customers and negative queueing lengths. J. Appl. Prob. 30, 931–942.CrossRefGoogle Scholar
Henderson, W. and Taylor, P. G. (1999). State-dependent coupling of quasireversible nodes. To appear in Queueing Systems.Google Scholar
Henderson, W., Northcote, B. S. and Taylor, P. G. (1994a). Geometric equilibrium distributions for queues with interactive batch departures. Ann. Operat. Res. 48, 463–492.CrossRefGoogle Scholar
Henderson, W., Northcote, B. S. and Taylor, P. G. (1994b). State-dependent signaling in queueing networks. Adv. Appl. Prob. 26, 436–455.CrossRefGoogle Scholar
Henderson, W., Pearce, C. E. M., Pollett, P. K. and Taylor, P. G. (1992). Connecting internally balanced quasireversible Markov processes. Adv. Appl. Prob. 24, 934–959.CrossRefGoogle Scholar
Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley, New York.Google Scholar
Kelly, F. P. (1982). Networks of quasi-reversible nodes. In Applied Probability–Computer Science: The Interface, Vol. I, eds Disney, R. L. and Ott, T. J., pp. 3–26. Birkhauser, Boston, MA.CrossRefGoogle Scholar
Miyazawa, M. (1996). Stochastic bound and stability of discrete-time Jackson networks with batch movements. In Stochastic Networks: Stability and Rare Events, eds Glasserman, P., Sigman, K. and Yao, D. (Lecture Notes in Statist. 117). Springer, New York.Google Scholar
Miyazawa, M. and Taylor, P. G. (1997). A geometric product-form distribution for a queueing network with nonstandard batch arrivals and batch transfers. Adv. Appl. Prob. 29, 523–544.CrossRefGoogle Scholar
Serfozo, R. F. and Yang, B. (1998). Markov network processes with string transitions. Ann. Appl. Prob. 8, 793–821.CrossRefGoogle Scholar
Stoyan, D. (1983). Comparison Methods for Queues and Other Stochastic Models. John Wiley, New York.Google Scholar
Walrand, J. (1988). An Introduction to Queueing Networks. Prentice Hall, New Jersey.Google Scholar
Whittle, P. (1986). Systems in Stochastic Equilibrium. John Wiley, New York.Google Scholar