Using constraint programming to address the operational aircraft line maintenance scheduling problem

Maintenance plays a major role in air transport management. Airlines are looking to reduce aircraft unavailability. Optimizing maintenance is a perspective to increase the operational potential of aircraft and offers novel managerial implications. Maintenance tasks are traditionally organized in periodic blocks of activities. In the modern aviation, more and more maintenance jobs can be performed between two flights, which is called Line Maintenance Scheduling Problem (LMSP). The expected goal of our paper is to propose an operational schedule that can be directly executed by maintainers, i.e. assigning a start time to each elementary activity and a resource to perform it. This new problem is named Operational Aircraft Line Maintenance Scheduling Problem (OALMSP). A scheduling assistant could help airlines to reduce maintenance costs and resource management. Planners have to respect task deadlines imposed by regulations, precedence constraints between certain operations and also ensure the availability of resources in order to perform specific actions. This problem is an extension of a Resource Constrained Project Scheduling Problem (RCPSP). In this article, we propose an industrial application of an automatic aircraft line maintenance scheduler based on a Constraint Programming (CP) model. The flexibility of our approach means we can easily adapt to airline use cases without changing the properties of the model. The optimization problem is generally made up of several objectives ordered according to their importance. The objectives are respectively to plan as many tasks as possible according to their priority, then to minimize both the use of resources and the deviation time between scheduled dates and target dates of tasks. The lexicographical order enables the use of human reasoning and the management of business priorities. A constructive search strategy is designed to compute a satisfying schedule within an acceptable execution time for industry application. A practical use case based on real airline data is presented and the results are compared with those found by an industrial solver taken as a reference.