This paper presents a novel methodology for optimal maintenance scheduling of multi-unit systems under predictive maintenance (PdM) environment. A maintenance scheduling model for multi-unit system is established considering performance degradation of units, dynamic characteristics of the system, economic dependence and structural dependence between units, and constraints of maintenance resources. The deterioration of units is modeled by Weibull distribution. Three maintenance actions, as minor repair, imperfect overhaul and replacement are considered to arrange the PdM schedule of a system. The genetic algorithm based methodology is employed to obtain the near optimal scheduling which results in a relatively minimal maintenance cost rate. The scheduling results demonstrate that the proposed methodology is feasible and effective.