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


Dijkhuizen, Gerhard van and Harten, Aart van (1997) Optimal clustering of frequency-constrained maintenance jobs with shared set-ups. European Journal of Operational Research, 99 (3). pp. 552-564. ISSN 0377-2217

open access
Abstract: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.
Item Type:Article
Copyright:© 1997 Elsevier Science
Research Chair:
Research Group:
Link to this item:http://purl.utwente.nl/publications/20712
Official URL:https://doi.org/10.1016/S0377-2217(96)00320-7
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 124342