Fierce competition between airlines has led to the need of minimising airlines’ direct operating costs, where possible, while also ensuring quality of service. Given the large proportion of direct operating costs dedicated to aircraft maintenance, cooperation between airlines and their respective maintenance provider is paramount. However, there are, clearly, conflicting objectives which have to be resolved through negotiations. In this research, our aim is to develop a fast maintenance scheduling tool which could aid maintenance scheduling negotiations between the airlines and maintenance providers. Using preprocessing and two different interval MIP formulations we generate maintenance schedules (in airframe and engine checks) that maximise aircraft utilisation (flying hours, flight types and number of cycles) with limited workshop resources. Moreover, when a flight schedule does not provide enough maintenance opportunities (long turnaround times), we allow perturbations to the flight schedule or an aircraft rotation to create a feasible maintenance schedule. By updating the "maintenance requirement" according to precise flying hours between maintenance opportunities we ensure that the aircraft are airworthy at all times. Computational tests were run on real flight data over a planning horizon of a month. Results show that even with multiple airlines (34745 flights,1412 aircraft, 16 workshops) our solution procedure can obtain optimal maintenance schedules within minutes.