A new approach to maintenance scheduling of generating units (MSU) in competitive electricity markets was presented, which was formulated as a noncooperative game with complete information. The payoff of each generating company (Genco) was defined as the profit from the energy auction market minus maintenance cost and risk loss. The compensation fee of interruptible load was a part of the maintenance cost when the permitted maintenance capacity in the system was insufficient. Hourly energy auction was incorporated in the computation of both revenues from energy market and risk loss of maintenance strategy as a nested game. A new heuristic search algorithm for the calculation of the game equilibrium of MSU was presented, which coordinates the solutions of nonequilibrium, unique equilibrium and multiple equilibria. Numerical results for a two-Genco system and a realistic system were used to demonstrate the basic ideas and the applicability of the proposed method, as well as its computational efficiency.