Page 413 - A First Course In Stochastic Models

408 ALGORITHMIC ANALYSIS OF QUEUEING MODELS

9.8 FINITE-CAPACITY QUEUES

This section considers queueing systems having room for only a finite number
of customers. Each customer finding no waiting place available upon arrival is
rejected. A rejected customer is assumed to have no further influence on the system.
In finite-capacity systems the finite waiting room acts as a regulator on the queue
size and so no a priori assumption on the offered load is needed. A practical
problem of considerable interest is the calculation of the rejection probability. A
basic problem in telecommunication and production is the design of finite buffers
such that the rejection probability is below a prespecified value. In this section it
will be shown that the rejection probability for the finite-buffer model can often
be expressed in terms of the state probabilities for the corresponding infinite-buffer
model. This result greatly simplifies the calculation of the smallest buffer size such
that the rejection probability is below a prespecified value. Before discussing this
result in Section 9.8.2, we first discuss in Section 9.8.1 an approximation to the
state probabilities in the M/G/c/c + N queue.

9.8.1 The M/G/c/c + N Queue
The M/G/c/c queueing model has a Poisson input with rate λ, a general service-
time distribution, c identical servers and N waiting positions for customers to await
service. An arriving customer who finds all c servers busy and all N waiting places
occupied is rejected. A tractable exact solution of this model is only possible for
the case of a single server (M/G/1/N queue), the case of exponential services
(M/M/c/c + N queue) and the case of no waiting room (M/G/c/c queue). The
M/G/c/c queue (Erlang loss model) was discussed in detail in Section 5.2 and
the M/M/c/c + N queue was dealt with in Exercise 5.1.
In the M/G/c/c + N queue the service time S of a customer has a general
probability distribution function B(x) with B(0) = 0. No restriction is imposed on
the load factor ρ defined by ρ = λE(S)/c. Let {p j , 0 ≤ j ≤ N + c} denote the
limiting distribution of the number of customers present. The next theorem extends
the approximation that was given in Theorem 9.6.1 for the state probabilities in the
infinite-capacity M/G/c queue. An approximation to the waiting-time probabilities
(percentiles) in the M/G/c/c+N is outlined in Exercise 9.14. This approximation
is based on the approximation to the state probabilities.

Theorem 9.8.1 Under Assumption 9.6.1, the state probabilities p j are approxi-
mated by

app (cρ) j app
p = p , 0 ≤ j ≤ c − 1,
j j! 0
j
app app app
p = λp a p b j−k , c ≤ j ≤ N + c − 1,
j c−1 j−c + λ k
k=c