Total tardiness minimization in a parallel machine system with flexible periodic maintenance

This paper addresses the total tardiness minimization problem in a manufacturing environment made by m uniform parallel processors subjected to regular maintenance activities. According to the so-called flexible periodic maintenance strategy, the time between two consecutive maintenance periods on each machine must be lower than or equal to a certain time value. In order to cope with such scheduling issue, a hybrid metaheuristic procedure integrating features from genetic algorithm and local search is proposed. The devised optimization algorithm is compared against two alternative metaheuristics on the basis of two separate benchmarks of test cases, involving small- and large-sized instances, respectively. For small-sized examples, optimal solutions provided by a specifically developed mixed integer linear programming model are taken as reference. Numerical results, also supported by a non-parametric statistical analysis, demonstrate the superiority of the proposed optimization algorithm in solving the investigated scheduling problem.