Scheduling of generating units for preventive maintenance plays an important role in the capacity planning of power systems. Optimal scheduling can be obtained in exponential time, consequently, efforts have been directed toward devising approximation algorithms which find near-optimal schedule. Based on the observation that the maintenance scheduling task and the makespan minimization on parallel machines are equivalent problems, in this paper effective approximation algorithms are presented for the levelized reserve as well as the levelized risk scheduling. These heuristic algorithms are compared with local search methods (simulated annealing and genetic algorithms). A case study for the Hungarian Power System shows that the developed algorithms can achieve a Substantial levelization in the reliability indices over the planning horizon.