This research concerns the problem of scheduling aircraft maintenance tasks, that must be carried in multiple maintenance checks to keep the aircraft airworthy. During this research the allocation of maintenance tasks to their maintenance opportunities is referred to as the task allocation problem. It is a complex combinatorial problem that is solved daily by aircraft operators.We propose a novel two-stage framework capable of solving the task allocation problem, for an entire fleet. A Mixed-Integer Linear Programming (MILP) formulation was developed for both stages of the framework. In the first stage an exact method is used to pre-determine the workforce to allocate per day to each aircraft under maintenance. In the second stage, the task allocation problem is solved in- dependently for each aircraft, allocating task at the work shift level and per workforce skill. Moreover, an approximation algorithm is proposed, using bin packaging problem solution techniques, for both stages of the framework.Both stages were tested and validated using data of 45 aircraft from a European airline. The compu- tational performance of the approximation algorithm is benchmarked using a MILP formulation, solved with a commercial solver. Results indicate that the solution quality of the proposed algorithm remains excellent and runs up to 26 times faster than the exact method.This research is the first to present an optimization model to solve the maintenance task allocation problem, being solved at the work shift level. Furthermore, it presents a bin-packaging approximation algorithm that can be solved within minutes for the 45 aircraft fleet and a planning horizon of 4 years. The framework was validated in practice and the results give insights on the potential benefit of using such framework to solve this daily recurrent problem.