Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-23T02:34:01.478Z Has data issue: false hasContentIssue false
  • English
  • Français

A Geometric Product-Form Distribution for a Queueing Network by Non-Standard Batch Arrivals and Batch Transfers

Part of: Markov processes Special processes

Published online by Cambridge University Press:  01 July 2016

Masakiyo Miyazawa  and
Peter G. Taylor
Masakiyo Miyazawa*
Affiliation:
Science University of Tokyo
Peter G. Taylor*
Affiliation:
The University of Adelaide
*
∗ Postal address: Department of Information Science, Science University of Tokyo, Noda, Chiba 278, Japan.
∗∗ Postal address: Department of Applied Mathematics, The University of Adelaide, SA 5005, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a batch service discipline, called assemble-transfer batch service, for continuous-time open queueing networks with batch movements. Under this service discipline a requested number of customers is simultaneously served at a node, and transferred to another node as, possibly, a batch of different size, if there are sufficient customers there; the node is emptied otherwise. We assume a Markovian setting for the arrival process, service times and routing, where batch sizes are generally distributed.

Under the assumption that extra batches arrive while nodes are empty, and under a stability condition, it is shown that the stationary distribution of the queue length has a geometric product form over the nodes if and only if certain conditions are satisfied for the extra arrivals. This gives a new class of queueing networks which have tractable stationary distributions, and simultaneously shows that the product form provides a stochastic upper bound for the stationary distribution of the corresponding queueing network without the extra arrivals.

Keywords

MARKOVIAN QUEUEING NETWORKBATCH ARRIVALBATCH SERVICESTOCHASTIC ORDERGEOMETRIC DISTRIBUTIONPRODUCT-FORMSTATIONARY DISTRIBUTIONNEGATIVE CUSTOMER

MSC classification

Primary: 60K25: Queueing theory
Secondary: 60J27: Continuous-time Markov processes on discrete state spaces
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 29 , Issue 2 , June 1997 , pp. 523 - 544
Copyright
Copyright © Applied Probability Trust 1997 

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

[1] Boucherie, R. J. and Van Dijk, N. M. (1991) Product forms for queueing networks with state-dependent multiple job transitions. Adv. Appl. Prob. 23, 152–187.Google Scholar
[2] Chao, X. and Pinedo, M. (1993) On generalized networks of queues with positive and negative arrivals. Prob. Eng. Inf. Sci. 7, 301–304.Google Scholar
[3] Chao, X., Pinedo, M. and Shaw, D. (1996) A network of assembly queues with product-form solution. J. Appl. Prob. 33, 858–869.CrossRefGoogle Scholar
[4] Dunford, N. and Schwartz, N. J. (1958) Linear Operators. Part 1. Interscience, New York.Google Scholar
[5] Gelenbe, E. (1991) Product-form queueing networks with negative and positive customers. J. Appl. Prob. 28, 656–663.CrossRefGoogle Scholar
[6] Gelenbe, E. (1993) G-networks with signals and batch removal. Prob. Eng. Inf. Sci. 7, 335–342.Google Scholar
[7] Gelenbe, E. (1993) G-networks with triggered customer movement. J. Appl. Prob. 30, 742–748.CrossRefGoogle Scholar
[8] Gross, D. and Harris, C. M. (1985) Fundamentals of Queueing Theory. 2nd edn. Wiley, New York.Google Scholar
[9] 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
[10] Henderson, W. and Taylor, P. G. (1990) Product form in networks of queues with batch arrivals and batch services. Queueing Systems 6, 71–88.Google Scholar
[11] Henderson, W. and Taylor, P. G. (1991) Some new results of queueing networks with batch movement. J. Appl. Prob. 28, 409–421.CrossRefGoogle Scholar
[12] Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, New York.Google Scholar
[13] Kelly, F. P. (1982) Networks of quasi-reversible nodes. In Applied Probability Computer Science: The Interface. Vol. I. ed. Disney, R. L. and Ott, T. J. pp. 3–26.Google Scholar
[14] Kingman, J. F. C. (1970) Inequalities in the theory of queues. J. R. Statist. Soc. B. 32, 102–110.Google Scholar
[15] Kleinrock, L. (1975) Queueing Systems. Volume 1: Theory. Wiley, New York.Google Scholar
[16] Massey, W. A. (1987) Stochastic orderings for Markov processes on partially ordered spaces. Math. Operat. Res. 12, 350–367.CrossRefGoogle Scholar
[17] Miyazawa, M. (1994) On the characterization of departure rules for discrete-time queueing networks with batch movements and its applications. Queueing Systems 18, 149–166.Google Scholar
[18] Miyazawa, M. (1995) A note on my paper: On the characterization of departure rules for discrete-time queueing networks with batch movements and its applications. Queueing Systems 19, 455–448.CrossRefGoogle Scholar
[19] Miyazawa, M. and Wolff, W. R. (1996) Symmetric queues with batch departures and their networks. Adv. Appl. Prob. 28, 308–326.CrossRefGoogle Scholar
[20] Serfozo, R. F. (1989) Poisson functionals of Markov processes and queueing networks. Adv. Appl. Prob. 21, 595–616.Google Scholar
[21] Serfozo, R. F. (1993) Queueing networks with dependent nodes and concurrent movements. Queueing Systems 13, 143–182.CrossRefGoogle Scholar
[22] Stoyan, D. (1983) Comparison Methods for Queues and other Stochastic Models. Wiley, New York.Google Scholar