Increasing competition amongst airlines necessitates them to improve the efficiency of their operations. Even though maintenance, repair, and overhaul (MRO) represent a significant portion of an airline’s operational costs, aircraft maintenance scheduling is often still a manual process, producing suboptimal solutions. Airlines typically operate by congregating the bulk of the required maintenance tasks in extensive checks, called letter checks (A, B, C, or D). Letter checks require the aircraft to be taken out of operations and result in many tasks being executed before they are due, leading to more required maintenance over the aircraft's lifetime. The purpose of this study is to develop a methodology that provides flight routes to aircraft and plans the maintenance tasks individually within these routes over a given planning horizon with the objective of maximizing the utilization of the total remaining flying time of the fleet. To achieve this, tasks are planned as late as possible on overlays at a maintenance station, while being given a due date and a remaining number of legal flight hours that can be flown before execution is mandatory. For this purpose, we develop a mixed integer programming (MIP) model based on a city-day network representation. Because the computational burden of exact methods becomes too hefty for increasing problem sizes, several matheuristics have been developed to provide good solutions in quick fashion. The presented matheuristics either decompose the problem by aircraft or into time periods. The former constructs the flight routes and maintenance schedules aircraft per aircraft while the latter constructs them simultaneously in a rolling horizon fashion. For the rolling horizon matheuristics, several forecasting strategies have been designed as well. In an experimental study, one of the selected rolling horizon matheuristics was able to remove the need for aircraft to be taken out of operations for an A-check (the most frequently occurring letter-check), potentially saving up to \$ 7.2 million per aircraft over a time period of ten years. Furthermore, the lost flying time, incurred by planning maintenance tasks before they are due, was decreased by over 98\%, resulting in a higher utilization of the task intervals and less required maintenance over the aircraft's lifetime. Finally, the dissection of the A-check into its individual tasks led to a more phased maintenance schedule by attenuating the peaks in workload for the mechanics workforce. Our presented approach can be used by mid-sized airlines to optimize their maintenance schedules through increasing aircraft availability and reducing maintenance costs over the aircraft's lifetime.