Page 376 - A First Course In Stochastic Models

THE GI /G/1 QUEUE 371

probability that a customer arriving in steady state has to wait longer than a time τ
when service is in order of arrival. The result (9.4.7) can be shown to hold for the
M/M/c queue with impatient customers as well; see Boots and Tijms (1999). In
X
X
fact the result (9.4.7) applies to both the M /G/1 queue and the M /M/c queue
with impatient customers. In Section 9.8 the structural form (9.4.7) will again be
encountered in queueing systems with finite buffers. It will be seen that the loss
probabilities in a finite-buffer queue can often be expressed in terms of the solution
for the corresponding infinite-buffer queue. This finding is extremely useful from a
computational point of view: to analyse the finite-buffer model for different buffer
sizes it suffices to compute only once the solution for the infinite-buffer model.

9.5 THE GI /G/1 QUEUE

This section deals with the GI/G/1 queue in which the interarrival times and the
service times both have a general probability distribution. The server utilization ρ
is assumed to be smaller than 1. Computationally tractable results can be obtained
only for special cases. However, the exact results for simpler models may be used
as a basis for approximations to the complex GI/G/1 model; see also the discussion
in Section 9.7. The discussion will concentrate on the computation of the waiting-
time probabilities for the cases of phase-type services and phase-type arrivals. For
these cases the computational method is based on numerical Laplace inversion.
The embedded Markov chain method is an alternative approach when the service
times are distributed as a mixture of Erlangian distributions with the same scale
parameters. The probabilistic approach for this particular case will be discussed
first. The discussion below assumes that service is in order of arrival.

9.5.1 Generalized Erlangian Services
Suppose that the service-time density b(t) is given by
m i i−1 −µt
µ t e
b(t) = q i , t ≥ 0,
(i − 1)!
i=1
where q m > 0. In other words, with probability q i the service time of a customer
is the sum of i independent phases each having an exponential distribution with
mean 1/µ. Thus we can define the embedded Markov chain {X n } by

X n = the number of uncompleted service phases just before the arrival
of the nth customer.

Denoting by {π j , j = 0, 1, . . . } the equilibrium distribution of this Markov chain,
we find by the same arguments as used to derive (5.1.7) that
 
∞ k k
−µx (µx)
W q (x) = 1 − e  1 − π j  , x ≥ 0. (9.5.1)
k!
k=0 j=0