Decomposition approach for integrated production scheduling and maintenance planning on parallel machines

In modern industrial manufacturing, the high availability of production capacities is as important as it has never been before. To preserve it and hedge against delays due to random failure, preventive maintenance activities are needed. On the one hand, they restore the machine’s condition but on the other hand they block it for production. Thus, the maintenance times are traded off against the delays caused by failures. This is incorporated into an identical parallel-machine scheduling problem minimizing the maximal expected completion time. The problem presented can be decomposed in multiple ways to accelerate the solution process. At every individual machine, the scheduling of jobs and preventive maintenance activities can be efficiently solved using a Dantzig-Wolfe decomposition and a branch-and-price algorithm. For the assignment of jobs to machines, a Benders’ decomposition is used to utilize the lower bound information of the branch-and-price algorithm and combine it with combinatorial cuts. Therefore, the developed approach integrates a branch-and-price algorithm as subproblem of a Benders’ decomposition. Computational results as well as further ideas to improve the performance are discussed and the proposed approach shows good solving capabilities compared to the monolithic model.