This paper presents a Genetic Algorithm methodology for finding the optimum preventive maintenance schedule of generating units of GENCOs in a restructured power system. In this environment, management of GENCOs and grid is separated, each maximizing its own benefit. Therefore, the principle to draw up the unit maintenance scheduling will be changed significantly. The profit of GENCO is defined as the total profit, which is the sum of the individual units’ profits from the auctions over the horizon. So each GENCO hopes to schedule its maintenance on the weeks when the spot marginal price (SMP) is lower, so that maintenance investment loss (MIL) is minimized. Therefore, objective function for the GENCO is to sell electricity as much as possible, according to the market clearing price forecast. Various technical constraints such as generation capacity, duration of maintenances and maintenance continuity are being taken in to account. The objective function of ISO is to maximize the reliability throughout the weeks of year. Various constraints such as minimum net reserve, duration of maintenance are being taken in to account. Therefore there are two objective functions for finding an optimum maintenance schedule in restructured power systems. Each GENCO specifies optimum maintenance schedule according to its objective function and hands it over to ISO. The ISO compares its own reliability index with reliability index related to maintenance schedule of GENCOs. If they are close enough in terms of reliability, it will be approved; otherwise the ISO sets up incentives and disincentives for each period to encourage GENCOs to modify their maintenance schedule so that the difference between reliability indices obtained by objective function of ISO and the GENCOs is minimized.