A variable neighborhood search and mixed-integer programming models for a distributed maintenance service network scheduling problem

Ship maintenance service optimisation is of great significance for improving the competitiveness of shipbuilding enterprises. In this paper, we investigate a ship maintenance service scheduling problem considering the deteriorating maintenance time, distributed maintenance tasks, and limited maintenance teams. The objective is to minimise the service span. First, we construct an initial mixed-integer programming model for the studied problem. Then, through the property analysis of the problem with a single maintenance team, an exact scheduling algorithm is proposed. In addition, the lower bound of the problem with multiple maintenance teams is derived. A scheduled rule is developed to obtain the lower bound for the problem. Based on the property analysis, the original mixed-integer programming model is simplified to an improved mathematical programming model. Since the studied problem is NP-hard, this paper proposes two heuristic algorithms and an integrated metaheuristic algorithm based on the variable neighbourhood search to obtain approximate optimal solutions in a reasonable time. In computational experiments, the two models can solve problems on small scale, while metaheuristics can find approximately optimal solutions in each problem category. Moreover, the computational results validate the performance of the proposed integrated metaheuristic in terms of convergence and stability.