This paper presents a formulation of outage planning for electric power facilities treated as a combinatorial optimization problem considering power supply reliability. The indices are defined as power supply shortage assuming N-2 contingencies and transmission loss assuming N-1 contingencies. A lot of constraints are also introduced to this problem with respect to the allocation of outage works and the determination of system configurations. Since it is expected that solving the problem is so hard due to combinatorial explosions, we apply a distributed genetic algorithm (DGA) to obtain feasible solutions. Simulation is executed to the real test system. It seems that some results show good solutions from the viewpoint of reliability indices. However, it is not clear that how far these solutions are close to the optimal ones and that how many feasible solutions the proposed system can obtain retaining diversity of individuals. In order to confirm the quality of solutions, we evaluate these solutions by using skewness values. As a result, the DGAs contribute to improve the solutions compared with simple genetic algorithm (SGA).