Reducing overall substation cost and improving reliability are the two prime but often conflicting objectives of electric power distribution. Proper scheduling of substation preventive maintenance provides an effective means to tradeoff between these two objectives. Decision-varying Markov models relating the deterioration process with maintenance operations is proposed to predict the availability of individual component. Minimum cut-sets method is employed to identify the critical components and evaluate the overall reliability of substation. A multiobjective evolutionary algorithm is proposed to optimize the two objectives to provide Pareto-fronts or tradeoff curves for a holistic view of the conflicting relationships between them. Through simulations, abilities of our proposed algorithm are demonstrated for robust search towards optimal solutions for large-size distribution.