Page 302 - A First Course In Stochastic Models

296 SEMI-MARKOV DECISION PROCESSES

of a few fast servers and many slow servers. Another simple rule is the Bernoulli-
splitting rule. Under this rule each arrival is assigned with a given probability
p k to queue k (k = 1, . . . , n) irrespective of the queue lengths. This assignment
rule produces independent Poisson streams at the various queues, where queue k
receives a Poisson stream at rate λp k . The probabilities p k must satisfy p k = 1
k
and λp k < s k µ k for k = 1, . . . , n. This condition guarantees that no infinitely
long queues can build up. Under the Bernoulli-splitting rule it is easy to give an
explicit expression for the overall average number of customers in the system.
The separate queues act as independent queues of the M/M/s type. This basic
queueing model is discussed in Chapter 5. In the M/M/s queue with arrival rate
α and s exponential servers each with service rate µ, the long-run average number
of customers in the system equals
−1
s−1 k s
s
ρ(sρ) (sρ) (sρ)
L(s, α, µ) = 2 + + sρ,
s!(1 − ρ) k! s!(1 − ρ)
k=0
where ρ = α/(sµ). Under the Bernoulli-splitting rule the overall average number
of customers in the system equals
n

L(s k , λp k , µ k ). (7.5.1)
k=1
The best Bernoulli-splitting rule is found by minimizing this expression with respect
to p 1 , . . . , p n subject to the condition k p k = 1 and 0 ≤ λp k < s k µ k for
k = 1, . . . , n. This minimization problem must be numerically solved by some
search procedure (for n = 2, bisection can be used to find the minimum of a
unimodal function in a single variable).

Policy-improvement step

The problem of assigning the arrivals to one of the server groups is a Markov
decision problem with a multidimensional state space. The decision epochs are
the arrival epochs of new customers. The state of the system at a decision epoch
is an n-dimensional vector x = (i 1 , . . . , i n ), where i j denotes the number of
customers present in queue j. This description uses the memoryless property of
the exponential service times. The action a = k in state x means that the new
arrival is assigned to queue k. To deal with the optimality criterion of the long-run
average number of customers in the system, we impose the following cost structure
on the system. A cost at rate j is incurred whenever there are j customers in the
system. Then the long-run average cost per time unit gives the long-run overall
average number of customers in the system.
Denote by policy R (0) the best Bernoulli-splitting rule and let p (0) , k = 1, . . . , n
k
be the splitting probabilities associated with policy R (0) . We already pointed out
that the average cost for rule R (0) is easy to compute. Below it will be shown that
the relative values are also easy to obtain for rule R (0) . Let us first explain how to