The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.