Page 366 - A First Course In Stochastic Models

X
THE M /G/1 QUEUE 361
individually by a single server. The service times of the customers are independent
random variables with a common probability distribution function B(t). Denoting
by the random variable S the service time of a customer, it is assumed that the
server utilization ρ defined by

ρ = λβE(S)

is smaller than 1. The analysis for the M/G/1 queue can be extended to the
X
M /G/1 queue. In Section 9.3.1 we give an algorithm for the state probabilities.
The computation of the waiting-time probabilities is discussed in Section 9.3.2.

9.3.1 The State Probabilities

The stochastic process {L(t), t ≥ 0} describing the number of customers in the
system is regenerative. The process regenerates itself each time an arriving batch
finds the system empty. The cycle length has a continuous distribution with finite
mean. Thus the process {L(t)} has a limiting distribution {p j }. The probability
p j can be interpreted as the long-run fraction of time that j customers are in the
system. The probability p 0 allows for the explicit expression

p 0 = 1 − ρ. (9.3.1)

To see this, we apply the ‘reward principle’ that was used in Section 2.3 to obtain
Little’s formula. Assume that the system earns a reward at rate 1 whenever a
customer is in service. Then the average reward per time unit represents the fraction
of time that the server is busy. The long-run average reward earned per customer is
equal to E(S), while the long-run average arrival rate of customers is λβ. Hence the
long-run average reward earned per time unit equals λβE(S). The long-run fraction
of time that the server is busy equals 1−p 0 . This shows that 1−p 0 = λβE(S) = ρ.
A recursion scheme for the p j is given in the following theorem.

Theorem 9.3.1 The state probabilities p j satisfy the recursion
j j k

p j = λp 0 β s a j−s + λ p i β s a j−k , j = 1, 2, . . . , (9.3.2)
s=1 k=1 i=0 s>k−i

where
∞

a n = r n (t){1 − B(t)} dt, n = 0, 1, . . .
0
with r n (t) = P {a total of n customers will arrive in (0,t)}.

Proof The proof is along the same lines as the proof of Theorem 9.2.1. The only
modification is with respect to the up- and downcrossing relation (9.2.5). We now
use the following up- and downcrossing argument: the number of downcrossings