Scheduling Multi-Component Maintenance With a Greedy Heuristic Local Search Algorithm

Document Type


Publication Date





Computing Sciences and Computer Engineering


As many large-scale systems age, and due to budgetary and performance efficiency concerns, there is a need to improve the decision-making process for system sustainment, including maintenance, repair, and overhaul (MRO) operations and the acquisition of MRO parts. To help address the link between sustainment policies and acquisition, this work develops a greedy heuristic-based local search algorithm (GHLSA) to provide a system maintenance schedule for multi-component systems, coordinating recommended component maintenance times to reduce system downtime costs, thereby enabling effective acquisition. The proposed iterative algorithm aims to minimize the sum of downtime, earliness and tardiness costs of scheduling, which contains three phases: (1) the construction phase, which uses a heuristic to construct an initial partial solution, (2) an improvement phase, which aims to improve the partial solution generated in the construction phase, and finally, (3) a local search phase, which performs a local search technique to the partial solution found in the improvement phase. The proposed algorithm makes a trade-off between exploration and exploitation of solutions. The experimental results for small (10 jobs) and large size (50 jobs) problems indicate that GHLSA outperforms both genetic algorithm and simulated annealing approaches in terms of solution quality and is similar in terms of efficiency.

Publication Title

Soft Computing

First Page


Last Page


Find in your library