Scheduling Post-Disaster Repairs in Electricity Distribution Networks

Natural disasters, such as hurricanes, earthquakes, and large wind or ice storms, typically cause damages to a large number of components in electricity distribution networks. Since power cannot be restored until these damages are repaired, strategically scheduling the repairs by available crews could reduce the harm done to the affected community. Considering the radial structure of many distribution networks, we model this repair and restoration process as a scheduling problem with soft precedence constraints. As a benchmark, we first formulate this problem as a time-indexed integer linear program (LP) with valid inequalities. Three approximation algorithms with performance guarantees are then proposed to solve this problem: first, an LP-based list scheduling algorithm, second, a single to multi-crew repair schedule conversion algorithm, and third, a dispatch rule based on ρ-factors which can be interpreted as component importance measures. Numerical results validate the effectiveness of the proposed methods.