Flow Networks book cover

Flow Networks

Analysis and optimization of repairable flow networks, networks with disturbed flows, static flow networks and reliability networks

Repairable flow networks are a new area of research, which analyzes the repair and flow disruption caused by failures of components in static flow networks. This book addresses a gap in current network research by developing the theory, algorithms and applications related to repairable flow networks and networks with disturbed flows. The theoretical results presented in the book lay the foundations of a new generation of ultra-fast algorithms for optimizing the flow in networks after failures or congestion, and the high computational speed creates the powerful possibility of optimal control of very large and complex networks in real time. Furthermore, the possibility for re-optimizing the network flows in real time increases significantly the yield from real production networks and reduces to a minimum the flow disruption caused by failures. The potential application of repairable flow networks reaches across many large and complex systems, including active power networks, telecommunication networks, oil and gas production networks, transportation networks, water supply networks, emergency evacuation networks, and supply networks. 

The book reveals a fundamental flaw in classical algorithms for maximising the throughput flow in networks, published since the creation of the theory of flow networks in 1956. Despite the years of intensive research, the classical algorithms for maximising the throughput flow leave highly undesirable directed loops of flow in the optimised networks. These flow loops are associated with wastage of energy and resources and increased levels of congestion in the optimised networks.

Audience

Students, researchers, and professionals in engineering, computing, and mathematics who work with networks.

Hardbound, 320 Pages

Published: February 2013

Imprint: Elsevier

ISBN: 978-0-12-398396-1

Contents

  • CONTENTS

    PREFACE

    1. FLOW NETWORKS - EXISTING ANALYSIS APPROACHES AND LIMITATIONS

    1.1 Repairable flow networks and static flow networks
     1.2 Repairable flow networks and stochastic flow networks
     1.3 Networks with disturbed flows and stochastic flow networks
     1.4 Performance of repairable flow networks

    2.  FLOW NETWORKS AND PATHS. BASIC CONCEPTS, CONVENTIONS AND ALGORITHMS

     2.1 Basic concepts and conventions. Data structures for representing flow networks
     2.2 Pseudo-code conventions used in the algorithms
     2.3 Efficient representation of repairable flow networks with complex topology
     2.3.1 Representing the topology of a complex flow network by an adjacency matrix
     2.3.2 Representing the topology of a complex flow network by adjacency arrays
     2.4  Paths. Algorithms related to paths in flow networks
     2.4.1 Determining the shortest path from the source to the sink
     2.4.2 Determining all possible source-to-sink minimal paths
     2.5 Determining the smallest-cost paths from the source
     2.6 Topological sorting of networks without cycles
     2.7 Transforming flow networks


    3. KEY CONCEPTS, RESULTS AND ALGORITHMS RELATED TO STATIC FLOW NETWORKS

     3.1 Path augmentation in flow networks
     3.2. Bounding the maximum throughput flow by the capacity of s-t cuts
     3.3 A necessary and sufficient condition for a maximum throughput flow in a static network. The max-flow min-cut theorem
     3.4 Classical augmentation algorithms for determining the maximum throughput flow in networks
     3.5 General push-relabel algorithm for maximising the throughput flow in a network
     3.6 Applications
     3.7 Successive shortest-path algorithm for determining the maximum throughput flow at a minimum cost
     3.7.1 A solved example


    4. MAXIMISING THE THROUGHPUT FLOW IN SINGLE COMMODITY AND MULTI-COMMODITY NETWORKS. REMOVING PARASITIC DIRECTED LOOPS OF FLOW IN NETWORKS OPTIMISED BY CLASSICAL ALGORITHMS.
    4.1 Eliminating parasitic directed loops of flow in networks optimised by classical algorithms
    4.2 A two-stage augmentation algorithm for determining the maximum throughput flow in a network
    4.3 A new, efficient algorithm for maximising the throughput flow of useful commodity in a multi-commodity flow network
     4.4 Network flow transformation along cyclic paths

    5.  NETWORKS WITH DISTURBED FLOWS. DUAL NETWORK THEOREMS FOR NETWORKS WITH DISTURBED FLOWS. REOPTIMISING THE POWER FLOWS IN ACTIVE POWER NETWORKS IN REAL TIME

    5.1. Reoptimising the flow in networks with disturbed flows after edge failures and after choking the edge flows
    5.2. A fast augmentation algorithm for reoptimising the flow in a repairable network after an edge failure
    5.3  An algorithm for maximising the throughput flow of oil after an edge failure in multi-commodity oil production networks
    5.4  A high-speed control of large and complex active power distribution networks
    5.4.1 Optimal control of the power flows in active power distribution networks, after a contingency event
    5.4.2 Transforming an active power network, with distributed sources of generation and loads, into a single-source, single-sink network
    5.4.3 Appendix 5.A. Proof of Theorem 5.3


    6. THE DUAL NETWORK THEOREM FOR STATIC FLOW NETWORKS AND ITS APPLICATION FOR MAXIMISING THE THROUGHPUT FLOW

    6.1  Analysis of the draining algorithm for maximising the throughput flow in static networks
    6.2  The dual network theorem for static flow networks
    6.3  Improving the average running time of maximising the throughput flow in the dual network
    6.4 Application of the dual network theorem for determining the maximum throughput in a static flow network
     6.4.1 Solved examples
    6.5 Area of application of the proposed throughput flow maximisation algorithm
    6.5.1 Comparing the performance of the proposed algorithm with the performance of a conventional algorithm

    7. RELIABILITY OF THE THROUGHPUT FLOW. ALGORITHMS FOR DETERMINING THE THROUGHPUT FLOW RELIABILITY.

    7.1 Probability that an edge will be in a working state on demand
    7.1.1  Hazard rate. A general time to failure model
    7.1.2 Negative exponential distribution of the time to failure. Mean time to failure
    7.1.3  Other time to failure models
    7.2.  Probability of a source-to-sink flow on demand
    7.2.1 Analytical methods
    7.2.1.1 Analytical expressions for series and parallel arrangement of the edges
    7.2.1.2 Network reduction method
    7.2.1.3 Decomposition method
    7.2.2 Monte Carlo simulation methods

    7.3 Probability of a source-to-sink flow on demand, of specified magnitude


    8. RELIABILITY NETWORKS

    8.1 Series and parallel arrangement of the components in a reliability network
    8.2 Building reliability networks. Difference between a physical and logical arrangement
    8.3 Complex reliability networks which cannot be presented as a combination of series and parallel arrangements
    8.4 Evaluating the reliability of complex systems


    9. PRODUCTION AVAILABILITY OF REPAIRABLE FLOW NETWORKS

    9.1 Discrete-event solver for determining the production availability of repairable flow networks
    9.2. A fast algorithm for determining the production availability of repairable flow networks
    9.3 Comparing the performance of competing network topologies


    10. LINK BETWEEN TOPOLOGY, SIZE AND PERFORMANCE OF REPAIRABLE FLOW NETWORKS

    10.1   A software tool for analysis and optimisation of repairable flow networks
    10.2  A comparative method for improving the performance of repairable flow networks
    10.3 Investigating the impact of the network topology on the network performance
    10.4  Investigating the link between network topology and network performance by using conventional reliability analysis
    10.5   Degree of throughput flow constraint


    11. TOPOLOGY OPTIMISATION OF REPAIRABLE FLOW NETWORKS AND RELIABILITY NETWORKS

    11.1 Theoretical basis of the proposed method for topology optimisation
    11.2 Topology optimisation algorithm
    11.3 Solved examples
    11.3.1 Maximising the throughput flow within a specified cost for building the network
    11.3.2 Maximising the production availability within a specified cost for building the network
    11.4 Topology optimisation of reliability networks
    Appendix  11.A


    12. REPAIRABLE NETWORKS WITH MERGING FLOWS

    12.1 The need for improving the running time of discrete-event solvers for repairable flow networks
    12.2  An algorithm with linear running time for maximising the flow in a network with merging flows
    12.3  Optimising the topology of a repairable network with merging flows to minimise the losses from failures

    13. FLOW OPTIMISATION IN NON-RECONFIGURABLE REPAIRABLE FLOW NETWORKS

    13.1   Lost flow caused by edge failures
    13.2   Resistance of a path
    13.3  Cyclic paths. Necessary and sufficient conditions for minimising the lost flow in non-reconfigurable repairable flow networks
    13.4  Guaranteeing throughput flow associated with the smallest lost flow due to edge failures
    13.4.1 Non-reconfigurable networks with complex topology
    13.4.2 Non-reconfigurable networks with merging flows
    13.5 Determining the edge flows which minimise the probability of flow disruption caused by edge failures.


    14. VIRTUAL ACCELERATED LIFE TESTING OF REPAIRABLE FLOW NETWORKS

    14.1  Acceleration stresses and acceleration life models
    14.1.1 Arrhenius stress-life relationship and Arrhenius-type acceleration life models
    14.1.2 Inverse power law relationship (IPL) and IPL-type acceleration life models
    14.1.3 Eyring stress-life relationship and Eyring-type acceleration life models
    14.1.4 A motivation for the proposed method

    14.2  Determining the availability of a repairable system
    14.2.1 A solved test example
    14.2.2 Interpretation of the results

     

Advertisement

advert image