Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2025-01-03T20:50:01.020Z Has data issue: false hasContentIssue false
  • English
  • Français

Queues with paired customers

Published online by Cambridge University Press:  14 July 2016

Guy Latouche
Guy Latouche*
Affiliation:
Université Libre de Bruxelles
*
∗Postal address: Université Libre de Bruxelles, Faculté des Sciences, Laboratoire d'informatique Théorique, Campus Plaine, Boulevard du Triomphe, C.P. 212, B–1050 Bruxelles, Belgium.
Get access Rights & Permissions [Opens in a new window]

Abstract

Queueing systems with a special service mechanism are considered. Arrivals consist of two types of customers, and services are performed for pairs of one customer from each type. The state of the queue is described by the number of pairs and the difference, called the excess, between the number of customers of each class. Under different assumptions for the arrival process, it is shown that the excess, considered at suitably defined epochs, forms a Markov chain which is either transient or null recurrent. A system with Poisson arrivals and exponential services is then considered, for which the arrival rates depend on the excess, in such a way that the excess is bounded. It is shown that the queue is stable whenever the service rate exceeds a critical value, which depends in a simple manner on the arrival rates. For stable queues, the stationary probability vector is of matrix-geometric form and is easily computable.

Keywords

QUEUEING THEORYSERVICES BY PAIRSEXCESSCOMPUTATIONAL PROBABILITY
Type
Research Papers
Information
Journal of Applied Probability , Volume 18 , Issue 3 , September 1981 , pp. 684 - 696
Copyright
Copyright © Applied Probability Trust 

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

Footnotes

Research conducted in part while the author was visiting the University of Delaware.

References

[1] Bailey, N. (1954) On queueing processes with bulk services, J. R. Statist. Soc. B16, 80–87.Google Scholar
[2] Downton, F. (1955) Waiting time in bulk service queues. J. R. Statist. Soc. B17, 256–261.Google Scholar
[3] Feller, W. (1964) An Introduction to Probability Theory and its Applications, Vol. 1. Wiley, New York.Google Scholar
[4] Harrison, J. M. (1973) Assembly-like queues. J. Appl. Prob. 10, 354–367.Google Scholar
[5] Latouche, G. and Neuts, M. F. (1980) Efficient algorithmic solutions to exponential tandem queues with blocking. SIAM J. Algebraic and Discrete Methods 1, 93–106.Google Scholar
[6] Neuts, M. F. (1978) Markov chains with applications in queueing theory, which have a matrix-geometric invariant probability vector, Adv. Appl. Prob. 10, 185–212.Google Scholar
[7] Neuts, M. F. (1978) The M/M/1 queue with randomly varying arrival and service rates. Opsearch 15, 139–157.Google Scholar
[8] Neuts, M. F. (1980) The probabilistic significance of the rate matrix in matrix-geometric invariant vectors. J. Appl. Prob. 17, 291–296.Google Scholar
[9] Wallace, V. (1969) The Solution of Quasi Birth and Death Processes Arising from Multiple Access Computer Systems. , Technical Report No. 07742-6-T, Systems Engineering Laboratory, University of Michigan.Google Scholar