Machine Repair Model

One example of the use of a discrete time Markov chain to solve a problem in computer systems performance evaluation comes from the machine repair model. The machine repair model presented below is actually only one possible model from a family of models that can be used to look at the reliability and performance of a computer system consisting of one or more parts that can fail and be repaired.

The particular machine repair model we use in this example has a single computer that may fail, and a single repairman who services it when it does fail. The machine can be in any of five states:

TABLE 1
state
idle	not broken, but with no work to do
busy	actively processing a job
waiting	in the midst of processing a job but waiting for an I/O operation to complete
broken	some part of the system has failed, and the repairman has not arrived
in repair	some part of the system has failed, and the repairman is working to fix the problem

We can represent the system as a discrete time Markov chain with the following state transition probabilities (rows represent present states, columns represent next states):

TABLE 2
	idle	busy	waiting	broken	in repair
idle	0.05	0.93		0.02
busy	0.10	0.43	0.43	0.04
waiting		0.60	0.35	0.05
broken				0.80	0.20
in repair	0.75				0.25

Blanks indicate that it is not possible to make a transition directly between the two states.

Ordering states in the state probability vector as they appear above, we have the following single step transition probability matrix. P=(

0.05	0.93	0	0.02	0
0.10	0.43	0.43	0.04	0
0	0.60	0.35	0.05	0
0	0	0	0.80	0.20
0.75	0	0	0	0.25

) You should verify that this is an ergodic chain. Since the chain is finite, all you have to do is prove irreducibility and aperiodicity.

As shown in the module on solving discrete-time Markov chains, this chain can be solved using Matlab in several ways. One way to find the steady state probability vector in Matlab is to raise the matrix to a power such that the rows are all the same, to the precision you want. P²⁰=(

0.0797	0.4284	0.2834	0.1645	0.0439
0.0797	0.4284	0.2834	0.1645	0.0439
0.0797	0.4284	0.2834	0.1645	0.0439
0.0797	0.4284	0.2834	0.1645	0.0439
0.0797	0.4284	0.2834	0.1645	0.0439

)

A second way of solving this chain is to use the eigenvector approach.


          [v,d] = eig(P')

d=(

-0.2724	0	0	0	0
0	1.0000	0	0	0
0	0	0.1098	0	0
0	0	0	0.3157	0
0	0	0	0	0.7270

) The d matrix contains the eigenvalues of the P matrix (actually, the transpose of the P matrix, since we are looking for left eigenvectors). The second eigenvector in the v matrix corresponds to the second eigenvalue, which has value 1.


          v(:,2) = [-0.1458  -0.7832  -0.5181  -0.3007  -0.0802]

To find the actual steady state probability vector, we need to normalize the vector so that its elements sum to one:


          sum(v(:,2)) = -1.8280

          pi = v(:,2)/sum(v(:,2))

π=(

0.0797

0.4282

0.2834

0.1645

0.0439

)

Finally, we can find the solution directly as the solution of a set of linear equations. Begin by subtracting the identity matrix from the single-step probability transition matrix. J5 is the identity matrix of rank 5. P−J5=(

-0.95	0.93	0	0.02	0
0.10	-0.57	0.43	0.40	0
0	0.60	-0.65	0.05	0
0	0	0	-0.20	0.20
0.75	0	0	0	-0.75

) This matrix is singular, so replace one of the Chapman-Kolmogorov equations with the normalization equation. In this example, we will replace the equation for the "in repair" state (the last column). P1=(

-0.95	0.93	0	0.02	1
0.10	-0.57	0.43	0.40	1
0	0.60	-0.65	0.05	1
0	0	0	-0.20	1
0.75	0	0	0	1

) Now solve the set of five independent, simultaneous linear equations.


         pi = [0  0  0  0  1]/P1

π=(

0.0797

0.4282

0.2834

0.1645

0.0439

)

With these steady state probabilities, we can answer several questions of possible interest. For example, the fraction of time that the system is broken is the probability that the model is in either of the states broken or in repair, or 20.84% of the time.

We could improve the fraction of time that the system is not broken by either increasing its reliability (reducing the probability that the model makes a transition from state idle, busy, or waiting to state broken) or by reducing the time it takes the repairman to begin work on the system when it is broken. Suppose we take the latter approach. If we reduce the probability that the model makes the transition back to state broken given that it is in state broken from 0.8 to 0.2, we find that π=(0.0910,0.4887,0.3233,0.0469,0.0500)^T , and the machine is broken only 9.69% of the time.