We propose a criticality-based scheduling model for aircraft component replacements.We schedule maintenance for a fleet of aircraft, each equipped with a multi-component system. The maintenance schedule takes into account a limited stock of spare components and the Remaining-Useful-Life prognostics for the components. We propose a component replacement scheduling model with three stages of maintenance criticality: i) critical aircraft that are not airworthy due to a lack of sufficient operational components, ii) predictive alerts for expected component failures, and iii) non-critical aircraft with some failed components. An Adaptive Large Neighborhood Search (ALNS) algorithm is developed to solve this criticality-based aircraft maintenance planning problem. The framework is illustrated for a fleet of aircraft, each equipped with a k-out-of-N system of components. A predictive maintenance planning is obtained within an outstanding computational time (less than 6 seconds for a fleet of 50 aircraft). Moreover, it is shown that the proposed planning with 3-levels of criticality ensures aircraft airworthiness while making cost-efficient use of maintenance slots.