|
|
 |
| |
|
|
|
Scalable Optimization of Line Maintenance Scheduling: Comparative Analysis of MILP and Constraint Programming Formulations |
|
|
|
PP: 747-762 |
|
|
doi:10.18576/amis/200314
|
|
|
|
Author(s) |
|
|
|
Bilal Bataineh,
Mohamed Heshmat,
Abdelmoty M. Ahmed,
|
|
|
|
Abstract |
|
|
| Aircraft line maintenance scheduling is a critical operational challenge for airlines, requiring the coordination of repetitive mandatory tasks, non-mandatory inspections, and time-varying resource constraints within narrow maintenance windows at multiple airports. This paper proposes a compact time-indexed mixed-integer linear programming (MILP) model that minimizes weighted earliness and tardiness penalties while respecting complex precedence networks, non-simultaneity constraints, airport restrictions, and dynamic resource capacities.To address scalability limitations of time-indexed formulations for large fleets, we develop a constraint programming (CP) alternative using interval variables and cumulative resource functions, eliminating the variable explosion inherent in fine-grained temporal discretization. We conduct a rigorous computational comparison between the MILP (solved with Gurobi) and CP-SAT (Google OR-Tools) formulations across 14 real-world instances spanning 5–11 aircraft, 10–30 planning days, and 51– 331 maintenance tasks. Results demonstrate that while the MILP guarantees optimality for small-to-medium instances (< 150 tasks), the CP-SAT approach achieves solutions within 0.93% of optimality while reducing solution time by 43.6% on average and cutting memory usage by 42% for large-scale problems (> 200 tasks).We further extend both formulations to handle operational uncertainties— flight delays, unplanned corrective tasks, and resource absenteeism—through dynamic buffer management strategies. The proposed framework enables airlines to select the appropriate solver based on fleet size and time sensitivity: MILP for optimality-critical planning horizons and CP-SAT for rapid daily re-optimization under dynamic conditions. Our open-source implementation provides practitioners with a scalable decision support tool for robust line maintenance scheduling. |
|
|
|
|
|
|
|
