Page 308 - A First Course In Stochastic Models

302 SEMI-MARKOV DECISION PROCESSES

and b = 20. Try other numerical examples and investigate whether the optimal control rule
is characterized by integers L 0 , . . . , L M so that an arriving unit of raw material finding i
units present at station 1 is only accepted when less than L i units are present at station 2.
7.8 Consider the situation that two groups of servers share a common waiting room. The
first group consists of c 1 servers and the second group consists of c 2 servers. Customers
for the first group arrive according to a Poisson process with rate λ 1 and, independently of
this process, customers for the second group arrive according to a Poisson process with rate
λ 2 . Upon arrival of a new customer, a decision has to be made to accept or reject them.
An accepted customer keeps one place in the waiting room occupied until their service is
completed. The service times of the customers are exponentially distributed with a mean
1/µ 1 for a customer going to the first group and mean 1/µ 2 for a customer going to the
second group. Each server can handle only one customer at a time and serves only customers
for the group to which the server belongs. The goal is to find a control rule minimizing the
total average rejection rate. Develop a value-iteration algorithm for this control problem.
Solve for the numerical data c 1 = c 2 = 1, λ 1 = 1.2, λ 2 = 1, µ 1 = µ 2 = 1 and M = 15,
where M denotes the number of places in the waiting room. Try other numerical examples
and verify experimentally that the optimal control rule is characterized by two sequences
(r) (r)
{a , 0 ≤ r ≤ M} and {a , 0 ≤ r ≤ M} so that an arriving customer of type k finding r
1 2
(k)
customers of the other type present upon arrival is accepted only if less than a r customers
of the same type k are present and the waiting room is not full. This problem is based on
Tijms and Eikeboom (1986).
7.9 Consider the problem of designing an optimal buffer management policy in a shared-
memory switch with the feature that packets already accepted in the switch can be dropped
(pushed out). The system has two output ports and a finite buffer shared by the two output
ports. Packets of types 1 and 2 arrive according to independent Poisson processes with rates
λ 1 and λ 2 . Packets of type i are destined for output port i for i = 1, 2. At each of the
two output ports there is a single transmission channel. Each channel can transmit only one
packet at a time and the transmission time at output port i is exponentially distributed with
mean 1/µ i for i = 1, 2. Upon arrival of a new packet, the system has to decide whether to
accept the packet, to reject it, or to accept it and drop a packet of the other type. A packet
that is rejected or dropped is called a lost packet and has no further influence on the system.
The total buffer size is B and it is assumed that an accepted packet occupies a buffer place
until its transmission is completed. The goal is to find a control rule minimizing the overall
fraction of packets that are lost. Develop a value-iteration algorithm. Solve for the numerical
data λ 1 = 1, λ 2 = 10, µ 1 = 2, µ 2 = 20 and B = 12. Try other numerical examples and
investigate whether the optimal control rule has a specific structure. This problem is based
on Cidon et al. (1995).
7.10 Consider a two-server facility with heterogeneous servers. The faster server is always
available and the slower server is activated for assistance when too many customers are
waiting. Customers arrive according to a Poisson process with rate λ. The service facility
has ample waiting room. The service times of the customers are independent of each other
and have an exponential distribution. The mean service time is 1/µ 1 when service is provided
by the faster server and is 1/µ 2 for the slower server, where 1/µ 1 < 1/µ 2 . It is assumed
that the load factor λ/(µ 1 + µ 2 ) is less than 1. The slower server can only be turned off
when it has completed a service. The slower server cannot be on when the system is empty.
If the slower server is kept on while customers are waiting for service, it cannot remain idle.
Each server can handle only one customer at a time. Service is non-pre-emptive; that is, the
faster server cannot take over a customer from the slower server. A fixed cost of K ≥ 0 is
incurred each time the slower server is turned on and there is an operating cost of r > 0
per time unit the slower server is on. Also, a holding cost of h > 0 per time unit is incurred
for each customer in the system. The goal is to find a switching rule that minimizes the