Page 349 - A First Course In Stochastic Models

344 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

1 t
L q = lim L q (u) du (the long-run average number in queue)
t→∞ t 0
n
1
W q = lim D k (the long-run average delay in queue)
n→∞ n
k=1
n
1
W = lim U k (the long-run average wait in system).
n→∞ n
k=1
These long-run averages are constants with probability 1. The steady-state probabil-
ities p j and the steady-state waiting-time distribution function W q (x) are defined by

p j = lim P {L(t) = j}, j = 0, 1, . . .
t→∞
and
W q (x) = lim P {D n ≤ x}, x ≥ 0.
n→∞
These limits exist and represent proper probability distributions; see Theorem 2.2.4.
As pointed out in Section 2.2, it is often preferable to interpret p j and W q (x) as
the long-run fraction of time that j customers are in the system and as the long-run
fraction of accepted customers whose delay in queue is at most x. In batch-arrival
queues the above limits need not exist, while p j and W q (x) can still be defined as
long-run averages. The long-run averages L q and W q can be expressed in terms of
the state probabilities p j and the waiting-time probabilities W q (x):

c+N
∞

L q = (j − c)p j and W q = {1 − W q (x)} dx.
0
j=c
It is important to note that the distribution of the number of customers in the
system is invariant to the order of service, provided that the queue discipline is
service-time independent and work-conserving. Here ‘service-time independent’
means that the rule for selecting the next customer to be served does not depend
on the service time of a customer, while ‘work-conserving’ means that the work or
service requirement of a customer is not affected by the queue discipline. Queue
disciplines having these properties include first-come first-served, last-come first-
served and service in random order. The waiting-time distribution will obviously
depend on the order of service.
Let the random variable I n = 1 if the nth arrival is rejected and let I n = 0
otherwise. Then the long-run fraction of customers who are rejected is given by
the constant

n
1
P rej = lim I k .
n→∞ n
k=1