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

Max Witteman, Qichen Deng and Bruno F. Santos

European Journal of Operational Research, 2021, vol. 294, issue 1, 365-376

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%.

Keywords: Scheduling; Bin packing problem; Worst-fit decreasing; Task allocation; Aircraft maintenance (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000576
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:294:y:2021:i:1:p:365-376

DOI: 10.1016/j.ejor.2021.01.027

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().