Abstarct: With the growing need for reliable and cheap electric energy, management of production and consumption of energy has become very important. High investment for building new generating units and also other restrictions for developing the generating units has forced us to operate the available units efficiently. A proper maintenance of the available units prolongs the generating units' life and also increases the reliability of the power system while reducing the electricity cost. Therefore an appropriate maintenance scheduling is very crucial for the reliable operation of the generating units. Levelising the reserve in the planning horizon is chosen as the objective of maintenance scheduling under the manpower, load and maintenance window constraints. Genetic algorithm (GA) in combination with local search algorithms such as hill climbing technique (HCT), extremal optimization (EO), combination of GA-EO and GA-EO-HCT are applied into different locations of GA including initial population, mating pool, offspring created by crossover operator and offspring created by mutation operator to tackle the maintenance scheduling problem. The discussed methods are applied to a maintenance scheduling test problem which has 21 generating units. The obtained results show that combination of GA-EO-HCT as a local search gives the best results over other local search methods.