A bin packing approach to solve the aircraft maintenance task allocation problem

Max Witteman, Qichen Deng*, Bruno F. Santos

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

31 Citations (Scopus)
111 Downloads (Pure)

Abstract

This paper addresses the scheduling of aircraft maintenance tasks that must be carried out in multiple maintenance checks to keep a fleet of aircraft airworthy. The allocation of maintenance tasks to maintenance opportunities, also known as the task allocation problem (TAP), is a complex combinatorial problem that needs to be solved daily by maintenance operators. We propose a novel approach capable of efficiently solving the multi-year task allocation problem for a fleet of aircraft in a few minutes. We formulate this problem as a time-constrained variable-sized bin packing problem (TC-VS-BPP), extending the well-known variable-sized bin packing problem (VS-BPP) by adding deadlines, intervals, and arrivals for the repetition of tasks. In particular, we divide the planning horizon into variable size bins to which multidimensional tasks are allocated, subject to available labor power and task deadlines. To solve this problem, we propose a constructive heuristic based on the worst-fit decreasing (WFD) algorithm for TC-VS-BPP. The heuristic is tested and validated using the maintenance data of 45 aircraft from a European airline. Compared with the solution obtained with an approach using an exact method, the proposed heuristic is more than 30% faster for all the test cases discussed with the airline. Most of the cases have optimality gaps below 3%. Even for the extreme case, the optimality gap is still smaller than 5%.

Original languageEnglish
Pages (from-to)365-376
Number of pages12
JournalEuropean Journal of Operational Research
Volume294
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

  • Aircraft maintenance
  • Bin packing problem
  • Scheduling
  • Task allocation
  • Worst-fit decreasing

Fingerprint

Dive into the research topics of 'A bin packing approach to solve the aircraft maintenance task allocation problem'. Together they form a unique fingerprint.

Cite this