skip to main content

Title: Scheduling Post disaster Repairs in Electricity Distribution Networks with Uncertain Repair Times
Natural disasters, such as hurricanes, large wind and ice storms, typically require the repair of a large number of components in electricity distribution networks. Since power cannot be restored before the completion of repairs, optimally scheduling the available crews to minimize the cumulative duration of the customer interruptions reduces the harm done to the affected community. We have previously proposed approximation algorithms to schedule post-disaster repairs in electricity distribution networks with complete damage information [1]. In this paper, we extend our previous work to the case with incomplete damage information. We model this problem as scheduling a set of jobs with stochastic processing times on parallel identical machines in order to minimize the total weighted energization time. A linear programming (LP) based list scheduling policy is proposed and then analyzed in terms of theoretical performance.
; ; ; ;
Award ID(s):
Publication Date:
Journal Name:
ACM SIGMETRICS performance evaluation review
Sponsoring Org:
National Science Foundation
More Like this
  1. Large quantities of data which contain detailed condition information over an extended period of time should be utilized to prioritize infrastructure repairs. As the temporal and spatial resolution of monitoring data drastically increase by advances in sensing technology, structural health monitoring applications reach the thresholds of big data. Deep neural networks are ideally suited to use large representative training datasets to learn complex damage features. In the previous study of authors, a real-time deep learning platform was developed to solve damage detection and localization challenge. The network was trained by using simulated structural connection mimicking the real test object withmore »a variety of loading cases, damage scenarios, and measurement noise levels for successful and robust diagnosis of damage. In this study, the proposed damage diagnosis platform is validated by using temporally and spatially dense data collected by Digital Image Correlation (DIC) from the specimen. Laboratory testing of the specimen with induced damage condition is performed to evaluate the performance and efficiency of damage detection and localization approach.« less
  2. Home energy management system (HEMS) enables residents to actively participate in demand response (DR) programs. It can autonomously optimize the electricity usage of home appliances to reduce the electricity cost based on time-varying electricity prices. However, due to the existence of randomness in the pricing process of the utility and resident's activities, developing an efficient HEMS is challenging. To address this issue, we propose a novel home energy management method for optimal scheduling of different kinds of home appliances based on deep reinforcement learning (DRL). Specifically, we formulate the home energy management problem as an MDP considering the randomness ofmore »real-time electricity prices and resident's activities. A DRL approach based on proximal policy optimization (PPO) is developed to determine the optimal DR scheduling strategy. The proposed approach does not need any information on the appliances' models and distribution knowledge of the randomness. Simulation results verify the effectiveness of our proposed approach.« less
  3. d. Many of the infrastructure sectors that are considered to be crucial by the Department of Homeland Security include networked systems (physical and temporal) that function to move some commodity like electricity, people, or even communication from one location of importance to another. The costs associated with these flows make up the price of the network’s normal functionality. These networks have limited capacities, which cause the marginal cost of a unit of flow across an edge to increase as congestion builds. In order to limit the expense of a network’s normal demand we aim to increase the resilience of themore »system and specifically the resilience of the arc capacities. Divisions of critical infrastructure have faced difficulties in recent years as inadequate resources have been available for needed upgrades and repairs. Without being able to determine future factors that cause damage both minor and extreme to the networks, officials must decide how to best allocate the limited funds now so that these essential systems can withstand the heavy weight of society’s reliance. We model these resource allocation decisions using a two-stage stochastic program (SP) for the purpose of network protection. Starting with a general form for a basic two-stage SP, we enforce assumptions that specify characteristics key to this type of decision model. The second stage objective—which represents the price of the network’s routine functionality—is nonlinear, as it reflects the increasing marginal cost per unit of additional flow across an arc. After the model has been designed properly to reflect the network protection problem, we are left with a nonconvex, nonlinear, nonseparable risk-neutral program. This research focuses on key reformulation techniques that transform the problematic model into one that is convex, separable, and much more solvable. Our approach focuses on using perspective functions to convexify the feasibility set of the second stage and second order conic constraints to represent nonlinear constraints in a form that better allows the use of computational solvers. Once these methods have been applied to the risk-neutral model we introduce a risk measure into the first stage that allows us to control the balance between an efficient, solvable model and the need to hedge against extreme events. Using Benders cuts that exploit linear separability, we give a decomposition and solution algorithm for the general network model. The innovations included in this formulation are then implemented on a transportation network with given flow demand« less
  4. Memory capacity is a key bottleneck for training large scale neural networks. Intel® Optane DC PMM (persistent memory modules) which are available as NVDIMMs are a disruptive technology that promises significantly higher read bandwidth than traditional SSDs at a lower cost per bit than traditional DRAM. In this work we show how to take advantage of this new memory technology to minimize the amount of DRAM required without compromising performance significantly. Specifically, we take advantage of the static nature of the underlying computational graphs in deep neural network applications to develop a profile guided optimization based on Integer Linear Programmingmore »(ILP) called AutoTM to optimally assign and move live tensors to either DRAM or NVDIMMs. Our approach can replace 50% to 80% of a system's DRAM with PMM while only losing a geometric mean 27.7% performance. This is a significant improvement over first-touch NUMA, which loses 71.9% of performance. The proposed ILP based synchronous scheduling technique also provides 2x performance over using DRAM as a hardware-controlled cache for very large networks.« less
  5. Purpose Marine transportation has been faced with an increasing demand for containerized cargo during the past decade. Marine container terminals (MCTs), as the facilities for connecting seaborne and inland transportation, are expected to handle the increasing amount of containers, delivered by vessels. Berth scheduling plays an important role for the total throughput of MCTs as well as the overall effectiveness of the MCT operations. This study aims to propose a novel island-based metaheuristic algorithm to solve the berth scheduling problem and minimize the total cost of serving the arriving vessels at the MCT. Design/methodology/approach A universal island-based metaheuristic algorithm (UIMA)more »was proposed in this study, aiming to solve the spatially constrained berth scheduling problem. The UIMA population was divided into four sub-populations (i.e. islands). Unlike the canonical island-based algorithms that execute the same metaheuristic on each island, four different population-based metaheuristics are adopted within the developed algorithm to search the islands, including the following: evolutionary algorithm (EA), particle swarm optimization (PSO), estimation of distribution algorithm (EDA) and differential evolution (DE). The adopted population-based metaheuristic algorithms rely on different operators, which facilitate the search process for superior solutions on the UIMA islands. Findings The conducted numerical experiments demonstrated that the developed UIMA algorithm returned near-optimal solutions for the small-size problem instances. As for the large-size problem instances, UIMA was found to be superior to the EA, PSO, EDA and DE algorithms, which were executed in isolation, in terms of the obtained objective function values at termination. Furthermore, the developed UIMA algorithm outperformed various single-solution-based metaheuristic algorithms (including variable neighborhood search, tabu search and simulated annealing) in terms of the solution quality. The maximum UIMA computational time did not exceed 306 s. Research limitations/implications Some of the previous berth scheduling studies modeled uncertain vessel arrival times and/or handling times, while this study assumed the vessel arrival and handling times to be deterministic. Practical implications The developed UIMA algorithm can be used by the MCT operators as an efficient decision support tool and assist with a cost-effective design of berth schedules within an acceptable computational time. Originality/value A novel island-based metaheuristic algorithm is designed to solve the spatially constrained berth scheduling problem. The proposed island-based algorithm adopts several types of metaheuristic algorithms to cover different areas of the search space. The considered metaheuristic algorithms rely on different operators. Such feature is expected to facilitate the search process for superior solutions.« less