Scheduling Post-Disaster Repairs in Electricity Distribution Networks
Yushi Tan Feng Qiu Arindam K. Das Daniel S. Kirschen Payman Arabshahi Jianhui Wang






Scheduling Post-Disaster Repairs in Electricity Distribution Networks
    Yushi Tan, Feng Qiu, Arindam K. Das, Daniel S. Kirschen, 
 Payman Arabshahi, Jianhui Wang
    
=============================================================================================





§ ABSTRACT


Natural disasters, such as hurricanes, earthquakes and large wind or ice storms, typically require the repair of a large number of components in electricity distribution networks. Since power cannot be restored before these repairs have been completed, optimally scheduling the available crews to minimize the cumulative duration of the customer interruptions reduces the harm done to the affected community. Considering the radial network structure of the distribution system, this repair and restoration process can be modeled as a scheduling problem with soft precedence constraints. As a benchmark, we first formulate this problem as a time-indexed ILP with valid inequalities. Three practical methods are then proposed to solve the problem: (i) an LP-based list scheduling algorithm, (ii) a single to multi-crew repair schedule conversion algorithm, and (iii) a dispatch rule based on ρ-factors which can be interpreted as Component Importance Measures. We show that the first two algorithms are 2 and (2 - 1/m) approximations respectively. We also prove that the latter two algorithms are equivalent. Numerical results validate the effectiveness of the proposed methods.



§ KEYWORDS


Electricity distribution network, Natural disasters, Infrastructure resilience, Scheduling with soft precedence constraints, Time-indexed integer programming, LP-based list scheduling, Conversion algorithm, Component Importance Measure (CIM)



§ INTRODUCTION



Natural disasters, such as Hurricane Sandy in November 2012, the Christchurch Earthquake of February 2011 or the June 2012 Mid-Atlantic and Midwest Derecho, caused major damage to the electricity distribution networks and deprived homes and businesses of electricity for prolonged periods. Such power outages carry heavy social and economic costs. Estimates of the annual cost of power outages caused by severe weather between 2003 and 2012 range from $18 billion to $33 billion on average<cit.>.  Physical damage to grid components must be repaired before power can be restored<cit.>. Hurricanes often cause storm surges that flood substations and corrode metal, electrical components and wiring <cit.>. Earthquakes can trigger ground liquefaction that damage buried cables and dislodge transformers <cit.>. Wind and ice storms bring down trees, breaking overhead cables and utility poles <cit.>. As the duration of an outage increases, its economic and social costs rise exponentially. See <cit.> <cit.> for discussions of the impacts of natural disasters on power grids and <cit.> <cit.> for its impact on other infrastructures.


It is important to distinguish the distribution repair and restoration problem discussed in this paper from the blackout restoration problem and the service restoration problem. Blackouts are large scale power outages (such as the 2003 Northeast US and Canada blackout) caused by an instability in the power generation and the high voltage transmission systems. This instability is triggered by an electrical fault or failure and is amplified by a cascade of component disconnections. Restoring power in the aftermath of a blackout is a different scheduling problem because most system components are not damaged and only need to be re-energized. See <cit.> <cit.>

for a discussion of the blackout restoration problem and <cit.> for a mixed-integer programming approach for solving this problem.  On the other hand, service restoration focuses on re-energizing a part of the local, low voltage distribution grid that has been automatically disconnected following a fault on a single component or a very small number of components. This can usually be done by isolating the faulted components and re-energizing the healthy parts of the network using switching actions. The service restoration problem thus involves finding the optimal set of switching actions. The repair of the faulted component is usually assumed to be taking place at a later time and is not considered in the optimization model. Several approaches have been proposed for the optimization of service restoration such as heuristics <cit.> <cit.>, knowledge based systems <cit.>, and dynamic programming <cit.>.

Unlike the outages caused by system instabilities or localized faults, outages caused by natural disasters require the repair of numerous components in the distribution grid before consumers can be reconnected. The research described in this paper therefore aims to schedule the repair of a significant number of damaged components, so that the distribution network can be progressively re-energized in a way that minimizes the cumulative harm over the total restoration horizon. Fast algorithms are needed to solve this problem because it must be solved immediately after the disaster and may need to be re-solved multiple times as more detailed information about the damage becomes available. Relatively few papers address this problem. Coffrin and Van Hentenryck <cit.> propose an MILP formulation to co-optimize the sequence of repairs, the load pick-ups and the generation dispatch. However, the sequencing of repair does not consider the fact that more than one repair crew could work at the same time. Nurre et al. <cit.> formulate an integrated network design and scheduling (INDS) problem with multiple crews, which focuses on selecting a set of nodes and edges for installation in general infrastructure systems and scheduling them on work groups. They also propose a heuristic dispatch rule based on network flows and scheduling theory.

The rest of the paper is organized as follows. In Section 2, we define the problem of optimally scheduling multiple repair crews in a radial electricity distribution network after a natural disaster, and show that this problem is at least strongly 𝒩𝒫-hard. In Section 3, we formulate the post-disaster repair problem as an integer linear programming (ILP) using a network flow model and present a set of valid inequalities. Subsequently, we propose three polynomial time approximation algorithms based on adaptations of known algorithms in parallel machine scheduling theory, and provide performance bounds on their worst-case performance. A list scheduling algorithm based on an LP relaxation of the ILP model is discussed in Section 4; an algorithm which converts the optimal single crew repair sequence to a multi-crew repair sequence is presented in Section 5, along with a equivalent heuristic dispatch rule based on ρ-factors. In Section 6, we apply these methods to several standard test models of distribution networks. Section 7 draws conclusions.



§ PROBLEM FORMULATION




A distribution network can be represented by a graph G with the set of nodes N and the set of edges (a.k.a, lines) L. We assume that the network topology G is radial, which is a valid assumption for most electricity distribution networks. Let S ⊂ N represent the set of source nodes which are initially energized and D = N ∖ S represent the set of sink nodes where consumers are located. An edge in G represents a distribution feeder or some other connecting component. Severe weather can damage these components, resulting in a widespread disruption of power supply to the consumers. Let L^D and L^I = L ∖ L^D denote the sets of damaged and intact edges, respectively. Each damaged line l ∈ L^D requires a repair time p_l which is determined by the extent of damage and the location of l. We assume that it would take every crew the same amount of time to repair the same damaged line. Without any loss of generality, we assume that there is only one source node in G. If an edge is damaged, all downstream nodes lose power due to lack of electrical connectivity. In this paper, we consider the case where multiple crews work simultaneously and independently on the repair of separate lines, along with the special case where a single crew must carry all the repairs.  Finally, we make the assumption that crew travel times between damage sites are minimal and can be either ignored or factored into the component repair times. Therefore, our goal is to find a schedule by which the damaged lines should be repaired such that the aggregate harm due to loss of electric energy is minimized. We define this harm as follows:



    ∑_n ∈ Nw_nT_n,


where w_n is a positive quantity that captures the importance of node n and T_n is the time required to restore power at node n. 

The importance of a node can depend on multiple factors, including but not limited to, the amount of load connected to it, the type of load served, and interdependency with other critical infrastructure networks. For example, re-energizing a node supplying a major hospital should receive a higher priority than a node supplying a similar amount of residential load. Similarly, it is conceivable that a node that provides electricity to a water sanitation plant would be assigned a higher priority. These priority factors would need to be assigned by the utility companies and their determination is outside the scope of this paper. We simply assume knowledge of the w_n's in the context of this paper.

The time to restore node n, T_n, is approximated by the energization time E_n, which is defined as the time node n first connects to the source node. System operators normally need to consider voltage and stability issues before restoring a node. However, this is not a major issue in distribution networks. The operators progressively restore a radial distribution network with enough generation capacity back to its normal operating state. And even if a rigorous power flow model is taken into account, the actual demands after re-energization are not known and hard to forecast. As a result, we model network connectivity using a simple network flow model, i.e., as long as a sink node is connected to the source, we assume that all the load on this node can be supplied without violating any security constraint. For simplicity, we treat the three-phase distribution network as if it were a single phase system. Our analysis could be extended to a three-phase system using a multi-commodity flow model, as in <cit.>.





 §.§ Soft Precedence Constraints


We construct two simplified directed radial graphs to model the effect that the topology of the distribution network has on scheduling. The first graph, G^', is called the `damaged component graph'. All nodes in G that are connected by intact edges are contracted into a supernode in G^'. The set of edges in G^' is the set of damaged lines in G, L^D. From a computational standpoint, the nodes of G^' can be obtained by treating the edges in G as undirected, deleting the damaged edges/lines, and finding all the connected components of the resulting graph. The set of nodes in each such connected component represents a (super)node in G^'. The edges in G^' can then be placed straightforwardly by keeping track of which nodes in G are mapped to a particular node in G^'. The directions to these edges follow trivially from the network topology. G^' is useful in the ILP formulation introduced in Section <ref>.

The second graph, P, is called a `soft precedence constraint graph', which is constructed as follows. The nodes in this graph are the damaged lines in G and an edge exists between two nodes in this graph if they share the same node in G^'. Computationally, the precedence constraints embodied in P can be obtained by replacing lines in G^' with nodes and the nodes in G^' with lines. Such a graph enables us to consider the hierarchal relationship between damaged lines, which we define as soft precedence constraints.






A substantial body of research exists on scheduling with precedence constraints. In general, the precedence constraint i ≺ j requires that job i be completed before job j is started, or equivalently, C_j ≥ C_i, where C_j is the completion time of job j. Such precedence constraints, however, are not applicable in post-disaster restoration. While it is true that a sink node in an electrical network cannot be energized unless there is an intact path  (i.e., all damaged lines along that path have already been repaired) from the source (feeder) to this sink node, this does not mean that multiple lines on some path from the source to the sink cannot be repaired concurrently.


We keep track of two separate time vectors: the completion times of line repairs, denoted by C_l's, and the energization times of nodes, denoted by E_n's. While we have so far associated the term `energization time' with nodes in the given network topology, G, it is also possible to define energization times on the lines. Consider the example in Fig. <ref>. The precedence graph, P, requires that the line 650-632 be repaired prior to the line 671-692. If this (soft) precedence constraint is met, as soon as the line 671-692 is repaired, it can be energized, or equivalently, all nodes in SN_3 (nodes 692 and 675) in the damaged component graph, G^', can be deemed to be energized. The energization time of the line 671-692 is therefore identical to the energization times of nodes 692 and 675. Before generalizing the above example, we need to define some notations. Given a directed edge l, let h(l) and t(l) denote the head and tail node of l. Let l = h(l) → t(l) be any edge in the damaged component graph G^'. Provided the soft precedence constraints are met, it is easy to see that E_l = E_t(l), where E_l is the energization time of line l and E_t(l) is the energization time of the node t(l) in G. Analogously, the weight of node t(l), w_t(l), can be interpreted as a weight on the line l, w_l.
The soft precedence constraint, i ≺_S j, therefore implies that line j cannot be energized unless line i is energized, or equivalently, E_j ≥ E_i, where E_j is the energization time of line j.



Given any feasible schedule of post-disaster repairs, the energization time E_j always satisfies,

    E_j = i  ≼_S   jmax   C_i



So far, we have modeled the problem of scheduling post-disaster repairs in electricity distribution networks as a parallel machine scheduling with outtree soft precedence constraints in order to minimize the total weighted energization time, or equivalently, P | outtree  soft  prec |∑ w_j E_j, following Graham's notation in <cit.>.



 §.§ Complexity Analysis

In this section, we study the complexity of the scheduling problem P | outtree  soft  prec |∑ w_j E_j and show that it is at least strongly 𝒩𝒫-hard.

The problem of scheduling post-disaster repairs in electricity distribution networks is at least strongly 𝒩𝒫-hard.




We show this problem is at least strongly 𝒩𝒫-hard using a reduction from the well-known identical parallel machine scheduling problem P  || ∑ w_jC_j defined as follows,

P  || ∑ w_jC_j: Given a set of jobs J in which j has processing time p_j and weight w_j, find a parallel machine schedule that minimizes the total weighted completion time ∑ w_jC_j, where C_j is the time when job j finishes. P  || ∑ w_jC_j is strongly 𝒩𝒫-hard <cit.>.

Given an instance of P  || ∑ w_jC_j defined as above, construct a star network G_S with a source and | J | sinks. Each sink j has a weight w_j and the line between the source and sink j has a repair time of p_j. Whenever a line is repaired, the corresponding sink can be energized. Therefore the energization time of sink j is equal to the completion time of line j. If one could solve the problem of scheduling post-disaster repairs in electricity distribution networks to optimality, then one can solve the problem in G_S optimally and equivalently solve P  || ∑ w_jC_
j.





§ INTEGER LINEAR PROGRAMMING (ILP) FORMULATION



With an additional assumption in this section that all repair times are integers, we model the post-disaster repair scheduling problem using time-indexed decision variables (see ), x_l^t, where x_l^t = 1 if line l is being repaired by a crew at time period t. Variable y_l^t denotes the repair status of line l where y_l^t = 1 if the repair is done by the end of time period t - 1 and ready to energize at time period t. Finally, u_i^t = 1 if node i is energized at time period t. Let T denote the time horizon for the restoration efforts. Although we cannot know T exactly until the problem is solved, a conservative estimate should work. Since T_i = ∑_t=1^T (1 - u_i^t) by discretization, the objective function of eqn. <ref> can be rewritten as:


    minimize   ∑_t=1^T∑_i ∈ Nw_i(1 - u_i^t)


This problem is to be solved subject to two sets of constraints: (i) repair constraints and (ii) network flow constraints, which are discussed next. We mention in passing that the above time-indexed (ILP) formulation provides a strong relaxation of the original problem <cit.> and allows for modeling of different scheduling objectives without changing the structure of the model and the underlying algorithm.



 §.§ Repair Constraints


Repair constraints model the behavior of repair crews and how they affect the status of the damaged lines and the sink nodes that must be re-energized. The three constraints below are used to initialize the binary status variables y_l^t and u_i^t. Eqn. <ref> forces y_l^t=0 for all lines which are damaged initially (i.e., at time t=0) while eqn. <ref> sets y_l^t=1 for all lines which are intact. Eqn. <ref> forces the status of all source nodes, which are initially energized, to be equal to 1 for all time periods.


  y_l^1 = 0,      ∀l ∈L^D
 

  y_l^t = 1,      ∀l ∈L^I,   ∀t ∈[1,T]  

  u_i^t = 1,      ∀i ∈S,   ∀t ∈[1,T] 


where T is the restoration time horizon. The next set of constraints is associated with the binary variables x_l^t. Eqn. <ref> constrains the maximum number of crews working on damaged lines at any time period t to be equal to m, where m is the number of crews available.


    ∑_l ∈ L^Dx_l^t≤ m,  ∀ t ∈ [1,T]


Observe that, compared to the formulation in <cit.>, there are no crew indices in our model. Since these indices are completely arbitrary, the number of feasible solutions can increase in crew indexed formulations, leading to enhanced computation time. For example, consider the simple network i → j → k → l, where node i is the source and all edges require a repair time of 5 time units. If 2 crews are available, suppose the optimal repair schedule is: `assign team 1 to i → j at time t=0, team 2 to j → k at t=0, and team 1 to k → l' at t=5.  Clearly, one possible equivalent solution conveying the same repair schedule and yielding the same cost, is: `assign team 2 to i → j at t=0, team 1 to j → k at t=0, and team 1 to k → l at t=5'. In general, formulations without explicit crew indices may lead to a reduction in the size of the feasible solution set.


Although the optimal repair sequences obtained from such formulations do not natively produce the work assignments to the different crews, this is not an issue in practice because operators can choose to let a crew work on a line until the job is complete and assign the next repair job in the sequence to the next available crew (the first m jobs in the optimal repair schedule can be assigned arbitrarily to the m crews).















Finally, constraint eqn. <ref> formalizes the relationship between variables x_l^t and y_l^t.


It mandates that y_l^t cannot be set to 1 unless at least p_l number of x_l^τ's, τ∈ [1, t - 1], are equal to 1, where p_l is the repair time of line l.


    y_l^t≤1/p_l∑_τ=1^t-1 x_l^τ,  ∀ l ∈ L^D,  ∀ t ∈ [1,T]


While we do not explicitly require that a crew may not leave its current job unfinished and take up a different job, it is obvious that such a scenario cannot be part of an optimal repair schedule.








 §.§ Network flow constraints




We use a modified form of standard flow equations to simplify power flow constraints. Specifically, we require that the flows, originating from the source nodes (eqn. <ref>), travel through lines which have already been repaired (eqn. <ref>). Once a sink node receives a flow, it can be energized (eqn. <ref>).



     ∑_l ∈δ_G^-(i) f_l^t ≥0,      ∀t ∈[1,T],     ∀i ∈S  

  
     -M ×y_l^t ≤f_l^t ≤M ×y_l^t,      ∀t ∈[1,T],     ∀l ∈L  

  
  
  
     u_i^t ≤∑_l ∈δ_G^+(i) f_l^t - ∑_l ∈δ_G^-(i) f_l^t,      ∀t ∈[1,T],    ∀i ∈D

















In eqn. <ref>, M is a suitably large constant, which, in practice, can be set equal to the number of sink nodes, M = | D |. In eqn. <ref>, δ_G^+(i) and δ_G^-(i) denote the sets of lines on which power flows into and out of node i in G respectively.




















 §.§ Valid inequalities


Valid inequalities typically reduce the computing time and strengthen the bounds provided by the LP relaxation of an ILP formulation. We present the following shortest repair time path inequalities, which resemble the ones in <cit.>. A node i cannot be energized until all the lines between the source s and node i are repaired. Since the lower bound to finish all the associated repairs is ⌊SRTP_i/m⌋, where m denotes the number of crews available and SRTP_i denotes the shortest repair time path between s and i, the following inequality is valid:


    ∑_t=1^⌊SRTP_i/m⌋ - 1 u_i^t = 0,   ∀ i ∈ N


To summarize, the multi-crew distribution system post-disaster repair problem can be formulated as:


    minimize     eqn. <ref>
    subject to     eqns. <ref> ∼ <ref>











§ LIST SCHEDULING ALGORITHMS BASED ON LINEAR RELAXATION


A majority of the approximation algorithms used for scheduling is derived from linear relaxations of ILP models, based on the scheduling polyhedra of completion vectors developed in <cit.> and <cit.>. We briefly restate the definition of scheduling polyhedra and then introduce a linear relaxation based list scheduling algorithm followed by a worst case analysis of the algorithm.



 §.§ Linear relaxation of scheduling with soft precedence constraints













A set of valid inequalities for m identical parallel machine scheduling was presented in <cit.>:


    ∑_j ∈ A p_j C_j ≥ f(A) := 1/2m(∑_j ∈ A p_j)^2 + 1/2 ∑_j ∈ A p_j^2     ∀ A ⊂ N



The completion time vector C of every feasible schedule on m identical parallel machines satisfies inequalities (<ref>).


The objective of the post-disaster repair and restoration is to minimize the harm, quantified as the total weighted energization time. With the previously defined soft precedence constraints and the valid inequalities for parallel machine scheduling, we propose the following LP relaxation:


    C, Eminimize     ∑_j ∈ L^D w_j E_j 
    subject to     C_j ≥ p_j,   ∀ j ∈ L^D 
        E_j ≥ C_j,  ∀ j ∈ L^D 
        E_j ≥ E_i,  ∀ (i → j) ∈ P 
       ∑_j ∈ A p_j C_j ≥1/2m(∑_j ∈ A p_j)^2 + 1/2 ∑_j ∈ A p_j^2,   ∀ A ⊂ L^D


where P is the soft precedence graph discussed in Section <ref> (see also Fig. <ref>). Eqn. <ref> constrains the completion time of any damaged line to be lower bounded by its repair time, eqn. <ref> ensures that any line cannot be energized until it has been repaired, eqn. <ref> models the soft precedence constraints, and eqn. <ref> characterizes the scheduling polyhedron.

The above formulation can be simplified by recognizing that the C_j's are redundant intermediate variables. Combining eqns. <ref> and  <ref>, we have:


    ∑_j ∈ A p_j E_j  ≥ ∑_j ∈ A p_j C_j  ≥ 1/2m(∑_j ∈ A p_j)^2 + 1/2 ∑_j ∈ A p_j^2,   ∀ A ⊂ L^D


which indicates that the vector of E_j's satisfies the same valid inequalities as the vector of C_j's. After some simple algebra, the LP-relaxation can be reduced to:


    Eminimize     ∑_j ∈ L^D w_j E_j 
    subject to      E_j ≥ p_j,  ∀ j ∈ L^D 
        E_j ≥ E_i,  ∀ (i → j) ∈ P 
       ∑_j ∈ A p_j E_j ≥1/2m(∑_j ∈ A p_j)^2 + 1/2 ∑_j ∈ A p_j^2,   ∀ A ⊂ L^D


We note that although there are exponentially many constraints in the above model, the separation problem for these inequalities can be solved in polynomial time using the ellipsoid method as shown in <cit.>.



 §.§ LP-based approximation algorithm


List scheduling algorithms, which are among the simplest and most commonly used approximate solution methods for parallel machine scheduling problems <cit.>, assign the job at the top of a priority list to whichever machine is idle first. An LP relaxation provides a good insight into the priorities of jobs and has been widely applied to scheduling with hard precedence constraints. We adopt a similar approach in this paper. Algorithm <ref>, based on a sorted list of the LP midpoints, summarizes our proposed approach. We now develop an approximation bound for Algorithm <ref>.






Let E_j^H denote the energization time respectively of line j in the schedule constructed by Algorithm <ref>. Then the following must hold,


    E_j^H≤ 2 E_j^LP,   ∀ j ∈ L^D





Let S_j^H, C_j^H and E_j^H denote the start time, completion time respectively of some line j in the schedule constructed by Algorithm <ref>.

Define M := [M_j^LP: j = 1,2, … , | L^D |]. Let M̃ denote M sorted in ascending order, ℐ̃_j denote the position of some line j ∈ L^D in M̃, and { k: ℐ̃_k ≤ℐ̃_j, k ≠ j } := R denote the set of jobs whose LP midpoints are upper bounded by M_j^LP. First, we claim that S_j^H≤1/m ∑_i ∈ R p_i. To see why, split the set R into m subsets, corresponding to the schedules of the m crews, i.e., R = ⋃_k=1^mR^k. Since job j is assigned to the first idle crew and repairs commence immediately, we have:



    S_j^H = min{∑_i ∈ R^k p_i: k = 1,2, … m }≤1/m ∑_k=1^m∑_i ∈ R^k p_i = 1/m ∑_i ∈ R p_i   ,


where the inequality follows from the fact that the minimum of a set of positive numbers is upper bounded by the mean. Next, noting that M_j^LP = E_j^LP - p_j/2, we rewrite eqn. <ref> as follows:


    ∑_j ∈ A p_j M_j^LP≥1/2m(∑_j ∈ A p_j)^2,  ∀ A ⊂ L^D



Now, letting A = R,  we have:


    (∑_i ∈ R p_i) M_j^LP ≥ ∑_i ∈ R p_i M_i^LP ≥ 1/2m(∑_i ∈ R p_i)^2   ,


where the first inequality follows from the fact that M_j^LP≥ M_i^LP for any i ∈ R. Combining eqns. <ref> and <ref>, it follows that S_j^H≤ 2 M_j^LP. Consequently, C_j^H = S_j^H + p_j ≤ 2 M_j^LP + p_j = 2 E_j^LP. Then,


    E_j^H = i ≼_S jmax  C_i^H ≤i ≼ jmax  2E_i^LP = 2 E_j^LP ,

where the last equality follows trivially from the definition of a soft precedence constraint.



Algorithm <ref> is a 2-approximation.




Let E_j^* denote the energization time of line j in the optimal schedule. Then, with E_j^LP being the solution of the linear relaxation,


    ∑_j ∈ L^D w_j E_j^LP≤∑_j ∈ L^D w_j E_j^*


Finally, from eqns. <ref> and <ref>, we have:


    ∑_j ∈ L^D w_j E_j^H≤ 2  ∑_j ∈ L^D w_j E_j^LP≤ 2  ∑_j ∈ L^D w_j E_j^*






§ AN ALGORITHM FOR CONVERTING THE OPTIMAL SINGLE CREW REPAIR SEQUENCE TO A MULTI-CREW SCHEDULE





In practice, many utilities schedule repairs using a priority list <cit.>, which leaves much scope for improvement. We analyze the repair and restoration process as it would be done with a single crew because this provides important insights into the general structure of the multi-crew scheduling problem. Subsequently, we provide an algorithm for converting the single crew repair sequence to a multi-crew schedule, which is inspired by similar previous work in <cit.>, and analyze its worst case performance. Finally, we develop a multi-crew dispatch rule and compare it with the current practices of FirstEnergy Group <cit.> and Edison Electric Institute <cit.>.




 §.§ Single crew restoration in distribution networks


We show that this problem is equivalent to 1 | outtree |∑ w_jC_j, which stands for scheduling to minimize the total weighted completion time of N jobs with a single machine under `outtree' precedence constraints.  Outtree precedence constraints require that each job may have at most one predecessor. Given the manner in which we derive the soft precedence (see Section <ref>), it is easy to see that P will indeed follow outtree precedence requirements, i.e. each node in P will have at most one predecessor, as long as the network topology G does not have any cycles. We will show by the following lemma that the soft precedence constraints degenerate to the precedence constraints with one repair team.


Given one repair crew, the optimal schedule in a radial distribution system must follow outtree precedence constraints, the topology of which follows the soft precedence graph P.





Given one repair crew, each schedule can be represented by a sequence of damaged lines. Let i-j and j-k be two damaged lines such that the node (j,k) is the immediate successor of node (i,j) in the soft precedence graph P. Let π be the optimal sequence and π^' another sequence derived from π by swapping i-j and j-k. Denote the energization times of nodes j and k in π by E_j and E_k respectively. Similarly, let E_j^' and E_k^' denote the energization times of nodes j and k in π^'. Define f := ∑_n ∈ Nw_nE_n.

Since node k cannot be energized unless node j is energized and until the line between it and its immediate predecessor is repaired, we have E_k^' = E_j^' in π' and E_k > E_j in π. Comparing π and π^', we see that node k is energized at the same time, i.e., E_k^' = E_k, and therefore, E_j^' > E_j. Thus:


    f(π^') - f(π)     = (w_jE_j' + w_kE_k') - (w_jE_j + w_kE_k) 
        = w_j(E_j' - E_j) + w_k(E_k' - E_k) > 0



Therefore, any job swap that violates the outtree precedence constraints will strictly increase the objective function. Consequently, the optimal sequence must follow these constraints.



 It follows immediately from Proposition <ref> that:


Single crew repair and restoration scheduling in distribution networks is equivalent to 1 | outtree |∑_j w_jC_j, where the outtree precedences are given in the soft precedence constraint graph P.




 §.§ Recursive scheduling algorithm for single crew restoration scheduling


As shown above, the single crew repair scheduling problem in distribution networks is equivalent to 1 | outtree |∑ w_jC_j, for which an optimal algorithm exists <cit.>. We will briefly discuss this algorithm and the reasoning behind it. Details and proofs can be found in <cit.>.



Let J^D ⊆ L^D denote any subset of damaged lines. Define:


    w(J^D) := ∑_j ∈ J^D w_j,   p(J^D) := ∑_j ∈ J^D p_j,    q(J^D) := w(J^D)/p(J^D)


Algorithm <ref>, adapted from <cit.> with a change of notation, finds the optimal repair sequence by recursively merging the nodes in the soft precedence graph P. The input to this algorithm is the precedence graph P. Let N(P) = {1,2, …| N(P) |} denote the set of nodes in P (representing the set of damaged lines, L^D), with node 1 being the designated root. The predecessor of any node n ∈ P is denoted by pred(n). Lines 1-7 initialize different variables. In particular, we note that the predecessor of the root is arbitrarily initialized to be 0 and its weight is initialized to -∞ to ensure that the root node is the first job in the optimal repair sequence. Broadly speaking, at each iteration, a node j ∈ N(P) (j could also be a group of nodes) is chosen to be merged into its immediate predecessor i ∈ N(P) if q(j) is the largest. The algorithm terminates when all nodes have been merged into the root. Upon termination, the optimal single crew repair sequence can be recovered from the predecessor vector and the element A(1), which indicates the last job finished.




We conclude this section by noting that Algorithm <ref> requires the precedence graph P to have a defined root. However, as illustrated in Section <ref>, it is quite possible for P to be a forest, i.e., a set of disjoint trees. In such a situation, P can be modified by introducing a dummy root node with a repair time of 0 and inserting directed edges from this dummy root to the roots of each individual tree in the forest. This fictitious root will be the first job in the repair sequence returned by the algorithm, which can then be stripped off.












 §.§ Conversion algorithm and an approximation bound


A greedy procedure for converting the optimal single crew sequence to a multiple crew schedule is given in Algorithm <ref>. We now prove that it is a (2-1/m) approximation algorithm. We start with two lemmas that provide lower bounds on the minimal  harm for an m-crew schedule, in terms of the minimal harms for single crew and ∞-crew schedules. Let H^1,∗, H^m,∗ and H^∞,∗  denote the minimal harms when the number of repair crews is 1, some arbitrary m (2 ≤ m < ∞), and ∞ respectively.





H^m, *≥1/m  H^1, *




Given an arbitrary m-crew schedule S^m with harm H^m, we first construct a 1-crew repair sequence, S^1. We do so by sorting the energization times of the damaged lines in S^m in ascending order and assigning the corresponding sorted sequence of lines to S^1. Ties, if any, are broken according to precedence constraints or arbitrarily if there is none. By construction, for any two damaged lines i and j with precedence constraint i ≺ j, the completion time of line i must be strictly smaller than the completion time of line j in S^1, i.e., C_i^1 < C_j^1. Additionally, C_i^1 = E_i^1 because the completion and energization times of lines are identical for a 1-crew repair sequence which also meets the precedence constraints of P.

Next, we claim that E_i^1 ≤ m E_i^m, where E_i^1 and E_i^m are the energization times of line i in S^1 and S^m respectively.

In order to prove it, we first observe that:


    E_i^1 = C_i^1 = ∑_{j:  E_j^m ≤ E_i^m} p_j   ≤∑_{j:  C_j^m ≤ E_i^m} p_j   ,


where the second equality follows from the manner we constructed S^1 from S^m and the inequality follows from the fact that C_j^m ≤ E_j^m ⇒{j:  E_j^m ≤ E_i^m}⊆{j:  C_j^m ≤ E_i^m} for any m-crew schedule. In other words, the number of lines that have been energized before line i is energized is a subset of the number of lines on which repairs have been completed before line i is energized. Next, we split the set {j:C_j^m ≤ E_i^m} := R into m subsets, corresponding to the schedules of the m crews in S^m, i.e., R = ⋃_k=1^mR^k, where R^k is a subset of the jobs in R that appear in the k^th crew's schedule. It is obvious that the sum of the repair times of the lines in each R^k can be no greater than E_i^m. Therefore,


    E_i^1 ≤∑_{j:  C_j^m ≤ E_i^m} p_j := ∑_j ∈ R p_j = ∑_k=1^m (∑_j ∈ R^k p_j) ≤ m E_i^m


Proceeding with the optimal m-crew schedule S^m,∗ instead of an arbitrary one, it is easy to see that E_i^1 ≤ m E_i^m,∗, where E_i^m,∗ is the energization time of line i in S^m,∗. The lemma then follows straightforwardly.


    H^m, * = ∑_i ∈ L^D w_i E_i^m,*≥∑_i ∈ L^D w_i  1/m  E_i^1 = 1/m ∑_i ∈ L^D w_i   E_i^1 = 1/m  H^1 ≥1/m  H^1, *






H^m,∗≥ H^∞,∗




This is intuitive, since the harm is minimized when the number of repair crews is at least equal to the number of damaged lines. In the ∞-crew case, every job can be assigned to one crew. For any damaged line j ∈ L^D, C^∞_j = p_j and E^∞_j = max_i ≼ j C^∞_i = max_i ≼ j p_i. Also, C^m,∗_j ≥ p_j = C^∞_j and E^m,∗_j = max_i ≼ j C^m,∗_i ≥max_i ≼ j p_i = E^∞_j. Therefore:


    H^m, * = ∑_j ∈ L^D w_j E_j^m,*≥∑_j ∈ L^D w_j E^∞_j = H^∞,∗





Let E_j^m be the energization time of line j after the conversion algorithm is applied to the optimal single crew repair schedule. Then, ∀ j ∈ L^D, E_j^m≤1/m  E_j^1,∗ + m-1/m  E^∞,∗_j. 




Let S_j^m and C_J^m  denote respectively the start and energization times of some line j ∈ L^D in the m-crew repair schedule, S^m, obtained by applying the conversion algorithm to the optimal 1-crew sequence, S^1,∗. Also, let ℐ_j denote the position of line j in S^1,∗ and {k: ℐ_k < ℐ_j} := R denote the set of all lines completed before j in S^1,∗. First, we claim that: S_j^m ≤1/m ∑_i ∈ R p_i. A proof can be constructed by following the approach taken in the proof of Proposition <ref> and is therefore omitted. Now:



    C_j^m    = S_j^m + p_j 
       ≤1/m ∑_i ∈ R p_i + p_j 
       = 1/m ∑_i ∈ R  ∪  j p_i + m-1/m  p_j 
        = 1/m  C_j^1,∗ + m-1/m  p_j


and


    E_j^m    = max_i ≼_S j C_i^m 
       ≤max_i ≼ j1/m  C_i^1,∗ + max_i ≼ jm-1/m  p_i 
       = 1/m  C_j^1,∗ + m-1/m max_i ≼ j p_i 
       = 1/m  E_j^1,∗ + m-1/m  E^∞,∗_j




The conversion algorithm is a (2 - 1/m)-approximation.






    H^m    = ∑_j ∈ L^D w_j E_j^m
       ≤∑_j ∈ L^D w_j (1/m E_j^1, * + m-1/mE^∞_j)   ⋯ using Proposition <ref>
       = 1/m ∑_j ∈ L^D w_j E_j^1, * +  m-1/m ∑_j ∈ L^D w_j E^∞_j 
       = 1/m  H^1, * + m-1/m  H^∞, *
       ≤1/m (m H^m, *) + m-1/m  H^m, *  ⋯ using Propositions <ref> - <ref>
       = (2 - 1/m) H^m, *






 §.§ A Dispatch Rule



We now develop a multi-crew dispatch rule from a slightly different perspective, and show that it is equivalent to the conversion algorithm. In the process, we define a parameter, ρ(l), ∀ l ∈ L^D, which can be interpreted as a `component importance measure' (CIM) in the context of reliability engineering. This allows us to easily compare our conversion algorithm to standard utility practices. Towards that goal, we revisit the single crew repair problem, in conjunction with the algorithm proposed in <cit.>.

Let S_l denote the set of all trees rooted at node l in P and s^*_l∈ S_l denote the minimal subtree which satisfies:


    ρ(l) := ∑_j ∈ N(s^∗_l) w_j/∑_j ∈ N(s^∗_l) p_j = max_s_l∈ S_l( ∑_j ∈ N(s_l) w_j/∑_j ∈ N(s_l) p_j) ,


where N(s_l) is the set of nodes in s_l. We define the ratio on the left-hand side of the equality in eqn. <ref> to be the ρ-factor of line l, denoted by ρ(l). We refer to the tree s^*_l as the minimal ρ-maximal tree rooted at l, which resembles the definitions discussed in <cit.>. With ρ-factors calculated for all damaged lines, the repair scheduling with single crew can be solved optimally, as stated in Algorithm <ref> below, adopted from <cit.>. Note that ρ-factors are defined based on the soft precedence graph P, whereas the following dispatch rules are stated in terms of the original network G to be more in line with industry practices.




It has been proven in <cit.> that Algorithms <ref> and <ref> are equivalent. The ρ-factors can be calculated in multiple ways: (1) following the method proposed in <cit.>, (2) as a byproduct of Algorithm <ref>, and (3) using a more general method based on parametric minimum cuts in an associated directed precedence graph <cit.>. Algorithm <ref> can be extended straightforwardly to accommodate multiple crews. However, in this case, it could happen that the number of damaged lines that are connected to energized nodes is smaller than the number of available repair crews. To cope with this issue, we also consider the lines which are connected to the lines currently being repaired, as described in Algorithm <ref> below.




Algorithm <ref> is equivalent to Algorithm <ref> discussed in Section <ref>.




As stated above, Algorithms <ref> and <ref> are both optimal algorithms and we assume that, without loss of generality, they produce the same optimal sequences. Then it suffices to show that Algorithm <ref> converts the sequence generated by Algorithm <ref> in the same way that Algorithm <ref> does to Algorithm <ref>.

The proof is by induction on the order of lines being selected. In iteration 1, it is obvious that Algorithms <ref> and <ref> choose the same line for repair. Suppose this is also the case for iterations 2 to t-1, with the lines chosen for repair being l_1, l_2, l_3, ⋯, and l_t-1 respectively. Then, in iteration t, the set of candidate lines for both algorithms is the set of immediate successors of the supernode {l_1, l_2, ⋯, l_t-1}. Both algorithms will choose the job with the largest ρ-factor in iteration t, thereby completing the induction process.




 §.§ Comparison with current industry practices



According to FirstEnergy Group <cit.>, repair crews will “address outages that restore the largest number of customers before moving to more isolated problems”. This policy can be interpreted as a priority-based scheduling algorithm and fits within the scheme of the dispatch rule discussed above, the difference being that, instead of selecting the line with the largest ρ-factor, FirstEnergy chooses the one with the largest weight (which turns out to be the number of customers). Edison Electric Institute <cit.> states that crews are dispatched to “repair lines that will return service to the largest number of customers in the least amount of time”. This policy is analogous to Smith's ratio rule <cit.> where jobs are sequenced in descending order of the ratios w_l/p_l, ensuring that jobs with a larger weight and a smaller repair time have a higher priority. The parameter, ρ(l), can be viewed as a generalization of the ratio w_l/p_l and characterizes the repair priority of some damaged line l in terms of its own importance as well as the importance of its succeeding nodes in P. Stated differently, ρ(l) can be interpreted as a broad component importance measure for line l. Intuitively, we expect a dispatch rule based on ρ(l) to work better than current industry practice since it takes a more holistic view of the importance of a line and, additionally, has a proven theoretical performance bound. Simulation results presented later confirm that a dispatch rule based on our proposed ρ-factors indeed results in a better restoration trajectory compared to standard industry practices.



§ CASE STUDIES


In this section, we apply our proposed methods to three IEEE standard test feeders of different sizes. We consider the worst case, where all lines are assumed to be damaged. In each case, the importance factor w of each node is a random number between 0 and 1, with the  exception of a randomly selected extremely important node with w = 5. The repair times are uniformly distributed on integers from 1 to 10. We compare the performances of the three methods, with computational time being of critical concern since restoration activities, in the event of a disaster, typically need to be performed in real time or near real time. All experiments were performed on a desktop with a 3.10 GHz Intel Xeon processor and 16 GB RAM. The ILP formulation was solved using Julia for Mathematical Programming with Gurobi 6.0.



 §.§ IEEE 13-Node Test Feeder


The first case study is performed on the IEEE 13 Node Test Feeder shown in Fig. <ref>, assuming that the number of repair crews is m=2. Since this distribution network is small, an optimal solution could be obtained by solving the ILP model. We ran 1000 experiments in order to compare the performances of the two heuristic algorithms w.r.t the ILP formulation.

Fig. <ref> shows the density plots of optimality gaps of LP-based list scheduling algorithm (LP) and the conversion algorithm (CA), along with the better solution from the two (EN). Fig. <ref> shows the optimality gaps when all repair times are integers. The density plot in this case is cut off at 0 since the ILP solves the problem optimally. Non-integer repair times can be scaled up arbitrarily close to integer values, but at the cost of reduced computational efficiency of the ILP. Therefore, in the second case, we perturbed the integer valued repair times by ± 0.1, which represents a reasonable compromise between computational accuracy and efficiency. The optimality gaps in this case are shown in Fig. <ref>. In this case, we solved the ILP using rounded off repair times, but the cost function was computed using the (sub-optimal) schedules provided by the ILP model and the actual non-integer repair times. This is why the heuristic algorithms sometimes outperform the ILP model, as is evident from Fig. <ref>. In both cases, the two heuristic algorithms can solve most of the instances with an optimality gap of  less than 10%. Comparing the two methods, we see that the conversion algorithm (CA) has a smaller mean optimality gap, a thinner tail, and a better worst case performance. However, this does not mean that the conversion algorithm is universally superior. In approximately 34% of the problem instances, we have found that the LP-based list scheduling algorithm yields a solution which is no worse than the one provided by the conversion algorithm.





 §.§ IEEE 123-Node Test Feeder


Next, we ran our algorithms on one instance of the IEEE 123-Node Test Feeder <cit.> with m=5. Since solving such problems to optimality using the ILP requires a prohibitively large computing time, we allocated a time budget of one hour. As shown in Table <ref>, both LP and HA were able to find a better solution than the ILP, at a fraction of the computing time.






 §.§ IEEE 8500-Node Test Feeder


Finally, we tested the two heuristic algorithms on one instance of the IEEE 8500-Node Test Feeder medium voltage subsystem <cit.> containing roughly 2500 lines, with m=10. We did not attempt to solve the ILP model in this case. As shown in Table <ref>, it took about more than 60 hours to solve its linear relaxation (which is reasonable since we used the ellipsoid method to solve the LP with exponentially many constraints) and the conversion algorithm actually solved the instance in two and a half minutes.

We also compared the performance of our proposed ρ-factor based dispatch rule to standard industry practices discussed in Section <ref>. We assign the same weights to nodes for all three dispatch rules. The plot of network functionality (fraction restored) as a function of time in Fig. <ref> shows the comparison of functionality trajectories. While the time to full restoration is almost the same for all three approaches, it is clear that our proposed algorithm results in a greater network functionality at intermediate times. Specifically, an additional 10% (approximately) of the network is restored approximately halfway through the restoration process, compared to standard industry practices.








 §.§ Discussion


From the three test cases above, we conclude that the ILP model would not be very useful for scheduling repairs and restoration in real time or near real time, except for very small problems. Even though it can be slow for large problems, the LP-based list scheduling algorithm can serve as an useful secondary tool for moderately sized problems. The conversion algorithm appears to have the best overall performance by far, in terms of solution quality and computing time.



§ CONCLUSION


In this paper, we investigated the problem of post-disaster repair and restoration in electricity distribution networks. We first proposed an ILP formulation which, although useful for benchmarking purposes, is feasible in practice only for small scale networks due to the immense computational time required to solve it to optimality or even near optimality. We then presented three heuristic algorithms. The first method, based on LP-relaxation of the ILP model, is proven to be a 2-approximation algorithm. The second method converts the optimal single crew schedule, solvable in polynomial time, to an arbitrary m-crew schedule with a proven performance bound of (2-1/m). The third method, based on ρ-factors which can be interpreted as component importance measures, is shown to be equivalent to the conversion algorithm. Simulations conducted on three IEEE standard networks indicate that the conversion algorithm provides very good results and is computationally efficient, making it suitable for real time implementation. The LP-based algorithm, while not as efficient, can still be used for small and medium scale problems.

Although we have focused on electricity distribution networks, the heuristic algorithms can also be applied to any infrastructure network with a radial structure (e.g., water distribution networks). Future work includes  development of efficient algorithms with proven approximation bounds which can be applied to arbitrary network topologies (e.g., meshed networks). While we have ignored transportation times between repair sites in this paper, this will be addressed in a subsequent paper. In fact, when repair jobs are relatively few and minor, but the repair sites are widely spread out geographically, optimal schedules are likely to be heavily influenced by the transportation times instead of the repair times. Finally, many  distribution networks contain switches that are normally open. These switches can be closed to restore power to some nodes from a different source. Doing so obviously reduces the aggregate harm. We intend to address this issue in the future.



