Including preventive maintenance activities in an unrelated parallel machine environment with dependent setup times

The assumption that machines are always available during the production horizon may not be true in real industrial settings. One of the main causes of machine unavailability is the failure of equipment and an efficient way to reduce the failure frequency is through preventive maintenance activities. From that the convenience of including preventive maintenance into the production planning process. In this paper we study a new scheduling problem on unrelated parallel machines that considers, in conjunction, preventive maintenance activities and setup times depending on the sequence and the machine. We present a mathematical formulation for this problem and derive valid inequalities to improve its performance, allowing to the model to obtain optimal solutions for small-medium instances. In addition, we design an efficient metaheuristic algorithm based on a multi-start strategy for solving larger instances. We carry out an extensive computational experimentation to investigate the scope of the model, to validate the influence of the valid inequalities and to assess the performance of the proposed algorithm.