This paper applies the Evolutionary Programming (EP) algorithm and a risk assessment technique to obtain an optimal solution to the Unit Maintenance Scheduling Decision (UMSD) problem subject to economic cost and power security constraints. The proposed approach employs a risk assessment model to evaluate the security of the power supply system and uses the EP algorithm to establish the optimal unit maintenance schedule. The effectiveness of the proposed methodology is verified through testing using the IEEE Reliability Test System (RTS). The test results confirm that the proposed approach can to ensure that the system security and outperforms the existing deterministic and stochastic optimization methods both in terms of the quality of the solution and the computational effort required. Therefore, the proposed methodology represents a particular effective technique for the UMSD.