Page 433 - A First Course In Stochastic Models

428 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

X
9.21 Consider the batch-arrival M /G/c/c + N queue with complete rejection. Suppose
that the batch size is a constant Q with 1 ≤ Q ≤ N + 1. Prove that the approximation
X
X
(9.8.13) to P rej is exact for both the M /G/1/N + 1 queue and the M /M/c/c + N
queue.
BIBLIOGRAPHIC NOTES

The queueing theory literature is voluminous. A good account of the basic theory is
provided by the books of Cooper (1991), Kleinrock (1975,1976) and Tak´ acs (1962).
A book emphasizing the analysis of the transient behaviour of queues is Newell
(1971). A thorough treatment of most of the background material in Section 9.1
can be found in the book of Wolff (1989). The regenerative approach used in
Sections 9.2 and 9.3 to analyse single-server queues with Poisson input has its
origin in the paper of Hordijk and Tijms (1976). This versatile approach was used
in Tijms et al. (1981) and Tijms and Van Hoorn (1982) to give an approximate
analysis of multi-server queues with state-dependent Poisson input; see also Van
Hoorn (1984). For finite-capacity queues of the M/G/1 type the structural form
for the rejection probability was noticed in the papers of Keilson and Servi (1989)
and Tijms and Van Ommeren (1989). The papers of Sakasegawa et al. (1993)
and Tijms (1992) provide theoretical and empirical support to this formula as an
approximation to a broad class of queueing systems; see also Gouweleeuw (1996).
The material on two-moment approximations for the minimal buffer size is based
on De Kok and Tijms (1985) and Gouweleeuw and Tijms (1996).

REFERENCES

Abate, J. and Whitt, W. (1992) Solving probability transform functional equations for numer-
ical inversion. Operat. Res. Lett., 12, 275–281.
Ackroyd, M.H. (1980) Computing the waiting-time distribution for the G/G/1 queue by
signal processing methods. IEEE Trans. Commun., 28, 52–58.
Anick, D., Mitra, D. and Sondhi, M.M. (1982) Stochastic theory of a data-handling system
with multiple sources. Bell Sys. Tech. J., 61, 1871–1894.
Boots, N.K. and Tijms, H.C. (1999) A multi-server queueing system with impatient cus-
tomers. Management Sci., 45, 444–448.
Boxma, O.J., Cohen, J.W. and Huffels, N. (1979) Approximations of the mean waiting time
in an M/G/s queueing system. Operat. Res., 27, 1115–1127.
Cohen, J.W. (1982) The Single Server Queue, 2nd edn. North-Holland, Amsterdam.
Cooper, R.B. (1991) Introduction to Queueing Theory, 2nd edn. North-Holland, Amsterdam.
Cosmetatos, G.P. (1976) Some approximate equilibrium results for the multi-server queue
M/G/r. Operat. Res. Quart., 27, 615–620.
Crommelin, C.D. (1932) Delay probability formulas when the holding times are constant.
Post Office Electr. Engng. J., 25, 41–50.
De Kok, A.G. (1984) Algorithmic methods for single server systems with repeated attempts.
Statistica Neerlandica, 38, 23–32.
De Kok, A.G. (1989) A moment-iterating method for approximating the waiting-time char-
acteristics of the GI/G/1 queue. Prob. Engng Inform. Sci., 3, 273–288.