Page 346 - A First Course In Stochastic Models

BASIC CONCEPTS 341

limited access of arrivals. In particular, attention is paid to approximations for
the rejection probability. Throughout this chapter numerical results are given in
order to provide insight into the performance of the solution methods. Indispens-
able tools for the solution of queues are the discrete Fast Fourier Transform (FFT)
method and numerical Laplace inversion. This is a remarkable twist in the history
of queueing analysis. The irony is that complaints about the ‘Laplacian curtain’
stimulated to a large extent the development of algorithmic analysis for queues.
Most of the results for queues in the post-war period were in terms of generat-
ing functions or Laplace transforms. For a long time it was believed that such
results were not very useful for computational purposes. However, the situation
dramatically changed with the invention of the discrete FFT method in 1965, one
of the greatest breakthroughs in numerical analysis. The power of this method
was directly realized in the field of engineering, but it took some time before the
immense usefulness of the discrete FFT method was recognized in the field of
applied probability as well.

9.1 BASIC CONCEPTS

In this section we discuss a number of basic concepts for queueing systems. The
discussion is restricted to queueing systems with only one service node. However,
the fundamental results below are also useful for networks of queues.
Let us start by giving Kendall’s notation for a number of standard queueing
models in which the source of population of potential customers is assumed to
be infinite. The customers arrive singly and are served singly. In front of the
servers there is a common waiting line. A queueing system having waiting room
for an unlimited number of customers can be described by a three-part code a/b/c.
The first symbol a specifies the interarrival-time distribution, the second symbol b
specifies the service-time distribution and the third symbol c specifies the number
of servers. Some examples of Kendall’s shorthand notation are:

1. M/G/1: Poisson (Markovian) input, general service-time distribution, 1 server.
2. M/D/c: Poisson input, deterministic service times, c servers.
3. GI/M/c: general, independently distributed interarrival times, exponential (Mar-
kovian) service times, c servers.
4. GI/G/c: general, independently distributed interarrival times, general service-
time distribution, c servers.

The above notation can be extended to cover other queueing systems. For
example, queueing systems have waiting room only for K customers (excluding
those in service) are often abbreviated by a four-part code a/b/c+K. The notation
X
GI /G/c is used for infinite-capacity queueing systems in which customers arrive
in batches and the batch size is distributed according to the random variable X.