Reducing the overall cost and improving the reliability are two primary but often conflicting objectives for composite power system. Scheduling of appropriate preventive maintenance requires optimization among multiple objectives. In this paper, an integrated methodology with three functional blocks is proposed. In the first block, the stochastic deterioration process of individual components is formulated as a maintenance-dependent continuous-time Markov model. Reliability of a composite power system is evaluated in the second block. In the third block, Pareto-based multiobjective evolutionary algorithm is proposed for providing a holistic view of conflicting relationships among multiple objectives. The second block extends the authors' original minimum cut sets, by identifying the loss of energy of a load point due to not only a loss of continuity within a substation, but also a loss of continuity and a violation of transfer limit between these substations. This work also extends the representation of maintenance activities to both maintenance timings and extents. The present approach is applied to the IEEE Reliability Test System (IEEE RTS) for optimizing its reliability, maintenance, and failure costs. Results demonstrate the potential of the present approach for handling complex systems, and substantiate its improvement over the authors' previously reported work.