Harmony search algorithm for single machine scheduling problem with planned maintenance

This paper focuses on the single machine scheduling problem, with sequence dependent setup times. Both processing and setup times are deterministic and the objective is to minimize total earliness and tardiness penalties. The novelty of the model can be traced in the fact that the single machine is subjected to breakdowns and that, in order to increase its availability, planned maintenance tasks are also performed. Hence, jobs and maintenance tasks are jointly considered to find the optimal schedule. These features make the problem NP-hard and so, a quasi-optimal solution is searched using a recent metaheuristic, which integrates harmony search and genetic algorithms. In order to validate the proposed metaheuristic, a comprehensive set of scheduling problems was fully investigated. Obtained results, compared with those of exhaustive (for small problems) and standard metaheuristics, confirm both the robustness and the speed of the proposed approach.