Multi-period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi-period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial-time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP-hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes.