Heuristics for the identical machine scheduling problem with preventive maintenances

In this paper, two mixed integer programming models integrating production scheduling and preventive maintenances are proposed to derive the optimal solutions for the identical machine scheduling problem with unavailability constraints. In the first model, the maintenance activities are performed periodically and the objective is to minimize the makespan. In the second model, the maintenance activities are flexible and the machines’ continuous working time cannot exceed a maximum allowed time T; the objective is to minimize the total completion time of jobs. For the first problem, we propose a heuristic longest batch time (LBT) and prove that the worst case error bound of LBT is 2. For the second problem, we develop a heuristic modified smallest processing time (MSPT) based on some properties of the optimal solutions. Computational experiments show that both of the heuristics are effective and efficient compared with the results obtained by CPLEX and the other algorithms.