A tabu search heuristic for building aircraft maintenance personnel rosters

This paper presents a fast heuristic approach to optimize staffing and scheduling of the workforce at an aircraft maintenance company. Two linked Tabu Search algorithms are proposed to minimize the labour costs and to maximize employee satisfaction. To enhance the performance of the algorithm, strategic oscillation and pattern creation are used. We illustrate the performance of the algorithms with a computational experiment based on real life data from Sabena Technics, a large aircraft maintenance company located at Brussels Airport in Belgium. We analyze the results in different scenarios and compare them to a mixed integer linear programming model. The experiments demonstrate that Tabu Search can deliver acceptable solutions faster than the integer programming technique for small instances and outperforms the integer programming model for larger and more realistic problem sizes.nrpages: 29status: publishe