Page 304 - A First Course In Stochastic Models

298 SEMI-MARKOV DECISION PROCESSES

The M/M/s queueing process can be seen as a Markov decision process with a
single decision in each state. The decision is to leave the system alone. In this
Markov decision formulation it is convenient to consider the state of the system both
at the arrival epochs and the service completion epochs. In the M/M/s queue the
situation of i customers present just after a service completion is probabilistically
the same as the situation of i customers present just after an arrival. In accordance
with (6.3.1), we define the relative cost function w(i) by

K(i) − gT (i), i = 1, 2, . . . ,
w(i) = (7.5.2)
0, i = 0,
where
T (i) = the expected time until the first return to an empty system starting
with i customers present,
K(i) = the total expected cost incurred until the first return to an empty
system starting with i customers present.
Then, by the economic interpretation of the relative values given in Section 6.3,
we have for any i = 0, 1, . . . that
w(i + 1) − w(i) = the difference in total expected costs over an infinitely long
period of time by starting in state i + 1 rather than in state i.
The desired function D k (i) for queue k follows by taking

D k (i) = w k (i + 1) − w k (i) with α = λp k , s = s k and µ = µ k .
The basic functions K(i) and T (i) are easy to compute. By conditioning,

1 α iµ
T i = + T i+1 + T i−1 , 1 ≤ i ≤ s. (7.5.3)
α + iµ α + iµ α + iµ
i α iµ
K i = + K i+1 + K i−1 , 1 ≤ i ≤ s. (7.5.4)
α + iµ α + iµ α + iµ
where T 0 = K 0 = 0. Further, we have

i − s
T i = + T s , i > s,
sµ − α
1 1 α(i − s) s(i − s)
K i = (i − s)(i − s − 1) + i − s + + , i > s.
sµ − α 2 sµ − α sµ − α
To see the latter relations, note that the time to reach an empty system from state
i > s is the sum of the time to reach state s and the time to reach an empty system
from state s. By the memoryless property of the exponential distribution, the multi-
server M/M/s queue operates as a single-server M/M/1 queue with service rate sµ
when s or more customers are present. Next, by applying the formulas (2.6.2) and
(2.6.3), we find the formulas for T i and K i when i > s. Substituting the expressions