New search algorithm for solving the maintenance scheduling problem for a family of machines

In many real-world applications, the cost associate with maintenance could be very significant since the maintenance work is subcontract or repairmen have to make a special trip from some central place to carry out the work. The focus of this study is to optimally coordinate the maintenance schedule of machines to save the maintenance cost incurred, which is named as the maintenance scheduling problem for a family of machines (MSPFM). Before presenting our solution approach, we first review Goyal and Kusy's model and their heuristic for solving the MSPFM. In this study, we conduct full analysis on the mathematical model for the MSPFM. By utilizing our theoretical results, we propose a new search algorithm that solves the optimal solution for the MSPFM very efficiently. Using 36,000 instances randomly generated, we show that our new search algorithm obtains better solutions than Goyal and Kusy's heuristic.