Optimal clustering of frequency-constrained maintenance jobs with shared set-ups

Since maintenance jobs often require one or more set-up activities, joint execution or clustering of maintenance jobs is a powerful instrument to reduce shut-down costs. We consider a clustering problem for frequency-constrained maintenance jobs, i.e. maintenance jobs that must be carried out with a prescribed (or higher) frequency. For the clustering of maintenance jobs with identical, so-called common set-ups, several strong dominance rules are provided. These dominance rules are used in an efficient dynamic programming algorithm which solves the problem in polynomial time. For the clustering of maintenance jobs with partially identical, so-called shared set-ups, similar but less strong dominance rules are available. Nevertheless, a surprisingly well-performing greedy heuristic and a branch and bound procedure have been developed to solve this problem. For randomly generated test problems with 10 set-ups and 30 maintenance jobs, the heuristic was optimal in 47 out of 100 test problems, with an average deviation of 0.24% from the optimal solution. In addition, the branch and bound method found an optimal solution in only a few seconds computation time on average.