A modified harmony search for the T-single machine scheduling problem with variable and flexible maintenance

A common assumption in the scheduling literature provides that machines are always available, while often they have to be stopped because of preventive maintenance operations. Inspired by a real-life manufacturing context, this paper deals with the single machine scheduling problem with a flexible/variable maintenance to be executed within a specific time window. Differently from other studies in the literature, a set of non-resumable jobs with sequence dependent setup-times and non-zero release dates have to be scheduled along with a maintenance activity whose duration is a non-decreasing function of its starting time, with the objective of minimizing the total tardiness (T-problem). A mathematical model of the problem is proposed and, due to the high computational complexity, several heuristics have been implemented and tested with the aim of using some of them to make metaheuristic algorithms more effective and computationally efficient. Hence, a modified harmony search, powered by several reinforcement strategies and even equipped with a self-adaptive calibration mechanism, has been developed and compared with a set of additional algorithms proposed by the literature. Numerical results reveal that the modified harmony search outperforms the competing algorithms and no performance loss arises by adopting the self-adaptive mechanism. Finally, a proper sensitivity analysis allows assessing the impact of several influencing factors on the total tardiness minimization.