Page 279 - A First Course In Stochastic Models

272 DISCRETE-TIME MARKOV DECISION PROCESSES

EXERCISES
6.1 Consider a periodic review production/inventory problem where the demands for a
single product in the successive weeks are independent random variables with a common
discrete probability distribution {φ(j), j = 0, . . . , r}. Any demand in excess of on-hand
inventory is lost. At the beginning of each week it has to be decided whether or not to start
a production run. The lot size of each production run consists of a fixed number of Q units.
The production lead time is one week so that a batch delivery of the entire lot occurs at
the beginning of the next week. Due to capacity restrictions on the inventory, a production
run is never started when the on-hand inventory is greater than M. The following costs are
involved. A fixed set-up cost of K > 0 is incurred for a new production run started after
the production facility has been idle for some time. The holding costs incurred during a
week are proportional to the on-hand inventory at the end of that week, where h > 0 is
the proportionality constant. A fixed lost-sales cost of p > 0 is incurred for each unit of
excess demand. Formulate the problem of finding an average cost optimal production rule
as a Markov decision problem.
6.2 A piece of electronic equipment having two identical devices is inspected at the beginning
of each day. Redundancy has been built into the system so that the system is still operating
if only one device works. The system goes down when both devices are no longer working.
The failure rate of a device depends both on its age and on the condition of the other device.
A device in use for m days will fail on the next day with probability r 1 (m) when the other
device is currently being overhauled and with probability r 2 (m) otherwise. It is assumed
that both r 1 (m) and r 2 (m) are equal to 1 when m is sufficiently large. A device that is found
in the failure state upon inspection has to be overhauled. An overhaul of a failed device
takes T 0 days. Also a preventive overhaul of a working device is possible. Such an overhaul
takes T 1 days. It is assumed that 1 ≤ T 1 < T 0 . At each inspection it has to be decided to
overhaul one or both of the devices, or let them continue working through the next day.
The goal is to minimize the long-run fraction of time the system is down. Formulate this
problem as a Markov decision problem. (Hint: define the states (i, j), (i, −k) and (−h−k).
The first state means that both devices are working for i and j days respectively, the second
state means that one device is working for i days and the other is being overhauled with
a remaining overhaul time of k days, and the third state means that both devices are being
overhauled with remaining overhaul times of h and k days.)
6.3 Two furnaces in a steelworks are used to produce pig iron for working up elsewhere
in the factory. Each furnace needs overhauling from time to time because of failure during
operation or to prevent such a failure. Assuming an appropriately chosen time unit, an
overhaul of a furnace always takes a fixed number of L periods. The overhaul facility is
capable of overhauling both furnaces simultaneously. A furnace just overhauled will operate
successfully during i periods with probability q i , 1 ≤ i ≤ M. If a furnace has failed, it must
be overhauled; otherwise, there is an option of either a preventive overhaul or letting the
furnace operate for the next period. Since other parts of the steelworks are affected when not
all furnaces are in action, a loss of revenue of c(j) is incurred for each period during which
j furnaces are out of action, j = 1, 2. No cost is incurred if both furnaces are working.
Formulate the problem of finding an average cost optimal overhauling policy as a Markov
decision problem. This problem is based on Stengos and Thomas (1980).
6.4 A factory has a tank for temporarily storing chemical waste. The tank has a capacity
3
3
of 4 m . Each week the factory produces k m of chemical waste with probability p k for
k = 0, . . . , 3 with p 0 = 1/8, p 1 = 1/2, p 2 = 1/4 and p 3 = 1/8. If the amount of waste
produced exceeds the remaining capacity of the tank, the excess is specially handled at a
cost of $30 per cubic metre. At the end of the week a decision has to be made as to whether
or not to empty the tank. There is a fixed cost of $25 to empty the tank and a variable cost