Page 412 - A First Course In Stochastic Models

THE GI/G/c QUEUE 407

where τ = e δD/c and δ is the unique solution of the equation

∞

e δD/c e −δx a(x) dx = 1 (9.7.24)
0
on the interval (0, ∞). Hence a finite system of linear equations is obtained for the
p j by replacing p j by p M τ −(j−M) for j ≥ M with M a sufficiently large integer.

Waiting-time probabilities

In general it is not possible to give a tractable algorithm for the waiting-time proba-
bilities in the GI/D/c queue. An exception is the E k /D/c queue. The waiting-time
probabilities in the E k /D/c queue are the same as the waiting-time probabilities
in the M/D/kc queue with the same server utilization as in the E k /D/c queue.

Theorem 9.7.1 The waiting-time distribution function W q (x) in the multi-server
GI/D/c queue is the same as in the single-server GI (c∗) /D/1 queue in which the
interarrival time is distributed as the sum of c interarrival times in the GI/D/c queue.

Proof Since the service times are deterministic, it is no restriction to cyclically
assign the customers to the c servers. Then server k gets the customers numbered as
k, k + c, k + 2c, . . . for k = 1, . . . , c. This simple observation proves the theorem.

The theorem has the following important corollary.

Corollary 9.7.2 The waiting-time distribution function W q (x) in the E k /D/c
queue is identical to the waiting-time distribution in the M/D/kc queue with the
same server utilization.

Proof An Erlang (k, α) distributed random variable has the same distribution as
the sum of k independent random variables each having an exponential distribution
with mean 1/α. Consider now the E k /D/c system with mean interarrival time
k/α and the M/D/kc system with mean interarival time 1/α. By Theorem 9.7.1,
both the waiting-time distribution in the E k /D/c system and the waiting-time
distribution in the M/D/kc system are the same as the waiting-time distribution
in the E ck /D/1 queue with mean interarrival time ck/α. This gives the desired
result.

What can be done for the case of a general interarrival-time distribution? Then
an approximation to the waiting-time probabilities can be computed by using Theo-
rem 9.7.1. The idea is to approximate the GI (c∗) /D/1 queue by an P h/D/1 queue
by replacing the interarrival-time distribution by a tractable phase-type distribution
that matches the first two or three moments. Section 9.5.4 discusses algorithms to
compute the waiting-time probabilities in the P h/D/1 queue.