Scheduling Maintenance Actions for Gas Turbines Aircraft Engines

Authors: Anis Gharbi

Abstract:

This paper considers the problem of scheduling maintenance actions for identical aircraft gas turbine engines. Each one of the turbines consists of parts which frequently require replacement. A finite inventory of spare parts is available and all parts are ready for replacement at any time. The inventory consists of both new and refurbished parts. Hence, these parts have different field lives. The goal is to find a replacement part sequencing that maximizes the time that the aircraft will keep functioning before the inventory is replenished. The problem is formulated as an identical parallel machine scheduling problem where the minimum completion time has to be maximized. Two models have been developed. The first one is an optimization model which is based on a 0-1 linear programming formulation, while the second one is an approximate procedure which consists in decomposing the problem into several two-machine subproblems. Each subproblem is optimally solved using the first model. Both models have been implemented using Lingo and have been tested on two sets of randomly generated data with up to 150 parts and 10 turbines. Experimental results show that the optimization model is able to solve only instances with no more than 4 turbines, while the decomposition procedure often provides near-optimal solutions within a maximum CPU time of 3 seconds.

Keywords: Aircraft turbines, Scheduling, Identical parallel machines, 0-1 linear programming, Heuristic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1091676

References:

[1] Haouari, M. andJemmali, M. (2007) "Maximizing the minimum completion time on parallel machines" 4 OR, 6, pp 375-392.
[2] Mokotoff, E. (2001) "Parallel machine scheduling problems: a survey", Asian Pacific Journal of Operational Research, 18 (2), pp 193-24.
[3] Tan, Z., He Y., Epstein L. (2004) "Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data", Information and Computation, 196, pp 57-70.
[4] Tan, Z. and He, Y. (2004) "Ordinal scheduling problem and its asymptotically optimal algorithms on parallel machine system", Science in Chaina Ser. F Information Sciences, 47 (2), pp 161-169.
[5] Woeginger, G. (1995) "A polynomial-time approximation scheme for maximizing the minimum machine completion time", Operations Research Letters, 20, pp149-154.