This paper uses a general maintenance problem and a new policy iteration algorithm to solve most semi-Markovian maintenance models. This algorithm decomposes the maintenance process into a deteriorating process and a sequence of replacement and repair actions so that the number of states involved in the decision process is less than the state space of the unmaintained process. Consequently, the number of equations to be solved at every iteration step can be substantially reduced.