This is assignment F of Caput Stochastic Optimalization
by Joeri van Hoeve (BWI'96)
First you'll see an executable version of my program in the
form of a calculator
Then I'll explain the model and backward
recursion
At last you can see the code of my backward
recursion algorithm
The long-run probability of call blocking in an
M/M/s/s system
This is a calculator, which calculates the long-run probability
of call blocking by using backward recursion. You must fill in the arrival
rate of calls per minute (default = 1) and the expected service time (default
= 5) and also the number of agents/lines in the system (default = 5) and
an epsilon (default = 0.0000000001). With the calculate button you'll get
the probability.
Service time: minutes
Number of agents/lines:
Epsilon:
Probability of long term call blocking: ,
M : the calls arrive according to the poisson-proces with
rate lambda
M : the service time is exponential, so the calls are served
with rate i*mu = i*(1/ES) ( i is the state you're in)
s : this means s agents in the model
s : this means s lines available, so no queue
(while #agents = #lines).
s+1 : states : number of calls in the system {0,1,2, .. s}
transition probabilities:
P(0,1) = P(s,s-1) = 1
P(i,i+1) = lambda/(lambda+i*mu) for i > 0
P(i,i-1) = (i*mu)/(lambda+i*mu) for i < s
The long-run probability of call blocking is the same (with
PASTA) as the average expected costs on the long run (the costs c(x) are
1 for being in state s and 0 for not being in state s). So we'll include
these costs in our model.
Then the average expected costs can be seen as the
fraction of time in state s on the long run and (with PASTA) this is the
same as the fraction of blocked calls.
We can make this conclusion only for constant expected
transition times T_x = tau_x. In this system the tau_x are not constant.
We can add dummy transitions and so taking an constant tau by assuming:
ETx = tau*Gx
0 < tau < tau_x for all x
Gx ~ geom(q_x) with q_x = tau / tau_x
Then the backward recursion is as follows:
Compute V_n+1(x) = c(x)*tau + q_x* sum_y {p(x,y) *
V_n(y)} + (1-q_x) * V_n(x) for all x;
with stopcriterium:
Span ( V_n+1(x) - V_n(x)) <= epsilon for all x
Then :
V_n+1(x) - V_n(x)/tau =
g for all x
and g = lim (V_t(x)/t for all x = expected
stationary costs = long-run probability of call blocking.