Long-term heavy maintenance check schedules are crucial in the aviation industry since airlines need them to prepare the required maintenance tools, workforce, and aircraft spare parts. However, most airlines adopt a manual approach to plan the heavy maintenance check schedules in current practice. This manual process relies on the experience of their maintenance planners, and the resulting heavy maintenance schedules need frequent adjustment because of uncertainty. This paper applies a genetic algorithm (GA) to generate robust aircraft heavy maintenance check schedules. It aims to reduce the workload and the frequency of revising heavy maintenance schedules considering uncertainties associated with heavy maintenance check duration and aircraft daily utilization. A major European airline case study shows that the GA finds robust and efficient multi-year aircraft heavy maintenance schedules for a fleet of 45 aircraft in 30 minutes. Compared with the current approach followed by the airline, the algorithm reduces the total number of heavy maintenance checks by 7% while increasing utilization by 4.4%, which could potentially lead to a reduction of direct annual maintenance costs between $122.5K and $612.5K. Furthermore, when testing the robustness of the 4-years maintenance check schedules produced, a Monte Carlo analysis has shown that all aircraft could be maintained before their check due date for 41% of the episodes simulated, compared to 0.27% of the episodes for the single deterministic scenario approach.@en