Abstract: To effectively reduce the operational costs of an airline fleet while ensuring flight safety, it is crucial to develop a scientific engine maintenance strategy. Through an in-depth analysis of civil aviation engine replacement and maintenance scenarios, a multi-objective mixed-integer programming model was constructed with the goal of minimizing maintenance costs and maximizing maintenance utility. The model investigates maintenance strategies for engines and their components, considering factors such as the distinct nature of different engines and resource constraints in maintenance workshops. To solve the multi-objective optimization model, an improved Non-dominated Sorting Genetic Algorithm II (NSGA-II) was designed, combining Particle Swarm Optimization (PSO) with NSGA-II to approximate the Pareto front of the model. A case study of a Chinese airline was used to validate the effectiveness of the model and algorithm through numerical experiments of different scales. Sensitivity analysis revealed valuable management insights. The results indicate that the number of life-limited parts and subcomponents in the engine significantly affect maintenance utility and costs.