Network Maintenance Scheduling with Maintenance Resource Constraints

Preventive maintenance is the main cause of interruptions of many real-world systems, such as communication, energy and logistics networks. Proper maintenance scheduling can greatly reduce the negative impact of interruptions, which achieved by alignment of various maintenance activities within the systems. In previous research, this problem was reduced to a Maximum Total Flow with Flexible Arc Outages (MaxTFFAO) and proved to be Strongly
$NP$
-hard. In this paper, we study the MaxTFFAO problem from a more practical perspective where resource limits are put on each maintenance job. This extended version is a quite typical scenario in practice because maintenance jobs require human or equipment resources, and those resources are not free. We first describe the problem mathematically with a mixed integer programming (MIP) model. Then an exact branch-and-cut algorithm is proposed based on Benders decomposition. To test the efficiency of this approach, we designed several sets of experimental data with various parameter settings. Computational analysis are conducted both on the testing and real-world data sets.