A new technique using a search method which is based on fuzzy multi-criteria function is proposed for GMS(generator maintenance scheduling) in order to consider multi-objective function. Not only minimization of probabilistic production cost but also maximization of system reliability level are considered for fuzzy multi-criteria function. To obtain an optimal solution for generator maintenance scheduling under fuzzy environment, fuzzy multi-criteria relaxation method(fuzzy search method) is used. The practicality and effectiveness of the proposed approach are demonstrated by simulation studies for a real size power system model in Korea in 2010.