Page 309 - A First Course In Stochastic Models

EXERCISES 303

long-run average cost per time unit. Using the embedding idea from Section 7.4, develop
a value-iteration algorithm for the control problem. Solve for the numerical data λ = 3,
µ 1 = 2.8, µ 2 = 2.2, h = 2, r = 4 and K = 10. Try other numerical examples and
verify experimentally that the optimal control rule is a so-called hysteretic (m, M) rule
under which the slower server is turned on when the number of customers present is M
or more and the slower server is switched off when this server completes a service and
the number of customers left behind in the system is below m. This problem is based
on Nobel and Tijms (2000), who developed a tailor-made policy-iteration algorithm for
this problem.
7.11 Consider again the heterogeneous server problem from Exercise 7.10. Assume now that
there are two slower servers in addition to the faster server, where the two slower servers
may have different speeds. The faster server is always available for service, while the slower
servers are activated for service when too many customers are present. The service time of
a customer is exponentially distributed with mean 1/µ i when service is provided by server
i. Server 1 is the faster server and servers 2 and 3 are the slower servers. It is assumed that
λ/(µ 1 + µ 2 + µ 3 ) < 1 and µ 1 > max(µ 2 , µ 3 ). There is an operating cost of r i > 0 per
time unit when the slower server i is on for i = 2, 3. A holding cost of h > 0 per time unit
is incurred for each customer in the system. There is no switching cost for turning either of
the slower servers on. Develop a value-iteration algorithm for this problem. Assuming that
the slower servers are numbered such that r 2 /µ 2 < r 3 /µ 3 , verify experimentally that the
optimal control rule is characterized by critical numbers 1 ≤ m 1 < m 2 and prescribes using
the slower server 2 when the number of customers present is more than m 1 , and using both
slow servers when the number of customers present is more than m 2 .
7.12 Messages arrive at a transmission channel according to a Poisson process with a con-
trollable arrival rate. The two possible arrival rates are λ 1 and λ 2 with 0 ≤ λ 2 < λ 1 . The
buffer at the transmission channel has ample space for temporarily storing arriving mes-
sages. The channel can only transmit one message at a time. The transmission time of each
message is exponentially distributed with mean 1/µ. It is assumed that λ 2 /µ < 1. At any
point in time it can be decided to change the arrival intensity from one rate to the other.
There is a fixed cost of K ≥ 0 for changing the arrival rate. An operating cost of r i > 0
per time unit is incurred when the prevailing arrival rate is λ i , i = 1, 2. Also, there is a
holding cost of h > 0 per time unit for each message awaiting service. The goal is to find
a control rule that minimizes the long-run average cost per time unit. Using the embedding
idea from Example 7.4.1, develop a value-iteration algorithm for this control problem. Solve
for the numerical data λ 1 = 4, λ 2 = 2, µ = 5, K = 5, r 1 = 1, r 2 = 10 and h = 2. Try
other numerical examples and investigate whether the optimal control rule has a specific
structure.
7.13 Customers of types 1 and 2 arrive at a shared resource according to independent
Poisson processes with respective rates λ 1 and λ 2 . The resource has c service units. An
arriving customer of type i requires b i service units. The customer is rejected when less
than b i units are available upon arrival. An accepted customer of type i immediately enters
service and has an exponentially distributed residency time with mean 1/µ i . During this
residency time the customer keeps all of the b i assigned service units occupied. These units
are released simultaneously when the customer departs. Develop a value-iteration algorithm
for the computation of a control rule that minimizes the total average rejection rate. Solve
for the numerical data c = 30, b 1 = 2, b 2 = 5, λ 1 = 6, λ 2 = 8, µ 1 = 1 and µ 2 = 0.5.
Try other numerical examples and verify experimentally that the optimal control rule can
(r) (r)
be characterized by two monotone sequences {a 1 } and {a 2 }. Under this control rule an
arriving customer of type i finding r customers of the other type present upon arrival is
(r)
accepted only when less than a i customers of the same type i are present and at least b i
service units are free.