A problem often encountered in operations management is that of determining an equipment replacement policy. Consider the simplified case of a factory that uses a single machine that degrades during use. We will assume that the state X_n of the machine at the beginning of the year n is an integer such that X_n S where S = {0, 1, 2, 3}. A machine in state 0 is perfectly productive, while a machine in state 3 is extremely expensive to maintain in operation. We denote by h(s) the annual cost of using a machine in state s. Two actions are possible at the beginning of year n: either action 0, which consists of keeping the same machine, or action 1, which consists of investing an amount C for the acquisition of a new machine. In both cases, we will assume that the factory will have a constant level of production which will yield an annual income R. For simplicity, we will assume that the new machine can be installed instantly and that it will be in state 0 of operation perfect, from the beginning of the year. During use, the condition of the machine deteriorates randomly. More precisely, we assume that a machine in state s at the beginning of the year and not replaced will be in state s + j at the beginning of the following year, j = 0, 1, . . . , 3 s, with probability q(j) if s + j < 3. A replaced machine behaves as if s = 0.

Suppose the annual discount rate is = 0.9, the annual income is R = 5, the cost of buying a new machine is C = 9, and the annual operating costs are h(0) = 1, h(1) = 2, h(2) = 5 and h(3) = 8 million dollars, and the wear probabilities are q(0) = 0.5, q(1) = 0.3 and q(2) = 0.2. Formulate this problem as a Makovian decision process and show that, for the expected discounted reward criterion, the optimal policy is to keep the machine if the state is 0 or 1, and to replace it if the state is 2 or 3. Suggestion: Do a number of dynamic programming iterations or use linear programming.