Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts

This paper proposes a performance index to measure the quality level of a stochastic-flow network in which each node has a designated capacity, which will have different lower levels due to various partial and complete failures. The performance index is the probability that the maximum flow of the network equals the demand d without exceeding the budget b. A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for (d, b), and then the probability that the maximum flow is less than or equal to d can be calculated in terms of such points. The upper boundary point for (d, b) is a maximal vector representing the capacity of each arc such that the maximum flow of the network under the budget b is d. The performance index can be calculated by repeating the proposed algorithm to obtain all upper boundary point for (d−1, b). A benchmark example is shown to illustrate the solution procedure.     

A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes

A MP/minimal cutset (MC) is a path/cut set such that if any edge is removed from this path/cut set, then the remaining set is no longer a path/cut set. An intuitive method is proposed to evaluate the reliability in terms of MCs in a stochastic-flow network subject to both edge and node failures under the condition that all of the MCs are given in advance. This is an extension of the best of known algorithms for solving the d-MC (a special MC but formatted in a system-state vector, where d is the lower bound points of the system capacity level) problem from the stochastic-flow network without unreliable nodes to with unreliable nodes by introducing some simple concepts. These concepts were first developed in the literature to implement the proposed algorithm to reduce the number of d-MC candidates. This method is more efficient than the best of known existing algorithms regardless if the network has or does not have unreliable nodes. Two examples are illustrated to show how the reliability is determined using the proposed algorithm in the network with or without unreliable nodes. The computational complexity of the proposed algorithm is analyzed and compared with the existing methods.     

A simple algorithm to generate all (d,B)-MCs of a multicommodity stochastic-flow network

Both minimal paths and minimal cuts are important media to evaluate the performance indexes, the system reliability or unreliability, for a single-commodity stochastic-flow network. This paper concentrates on a multicommodity stochastic-flow network in which each arc has both the capacity and cost attributes. Different from the single-commodity case, the system capacity is a pattern for multicommodity case. Since the traditional performance indexes are not suitable for multicommodity case, we propose a new performance index, the probability that the system capacity is less than or equal to a given pattern under the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MCs that are the maximal capacity vectors meeting the demand d and budget B. The proposed performance index can be evaluated in terms of (d,B)-MCs.     

A simple approach to search for all d-MCs of a limited-flow network

Many real-world systems are multistate systems composed of multistate components in which the reliability can be computed in terms of the lower bound points of level d, called d-MCs. Such systems (electric power, transportation, etc.) may be regarded as flow networks whose arcs have independent, discrete, limited and multivalued random capacities. In this study, all MCs are assumed to be known in advance and we focused on how to find the entire d-MCs before calculating the reliability value of a network. Just based on the definition of d-MC, we develop an intuitive algorithm which is better than the best-known existing method. Analysis of our algorithm and comparison to existing algorithms shows that our proposed method is easier to understand and implement. Finally, the computational complexity of the proposed algorithm is analysed and compared with the existing methods.     

Reliability of a computer network in case capacity weight varying with arcs, nodes and types of commodity

The computer network can be modeled as a capacitated-flow network. This paper concentrates on a two-commodity capacitated-flow network with three characters: (1) nodes as well as arcs have multiple possible capacities and may fail, (2) each component (arc/node) has both capacity and cost attributes; and (3) the capacity weight varies with arcs, nodes and types of commodity (or named file). We study the possibility that a given quantity of two types of files can be transmitted through this network simultaneously under the budget constraint. Such a possibility is named the system reliability which is a performance index to measure the quality level of supply demand systems such as computer, telecommunication, electric-power transmission and transportation systems. The approach of minimal paths is applied to describe the relationship among flow assignments and capacity vectors. A simple algorithm in terms of minimal paths is proposed to evaluate the system reliability.     

Evaluation of the reliability of transport networks based on the stochastic flow of moving objects

In transport networks, human beings are moving objects whose moving direction is stochastic in emergency situations. Based on this idea, a new model—stochastic moving network (SMN) is proposed. It is different from binary-state networks and stochastic-flow networks. The flow of SMNs has multiple-saturated states, that correspond to different flow values in each arc. In this paper, we try to evaluate the system reliability, defined as the probability that the saturated flow of the network is not less than a given demand d. Based on this new model, we obtain the flow probability distribution of every arc by simulation. An algorithm based on the blocking cutset of the SMN is proposed to evaluate the network reliability. An example is used to show how to calculate the corresponding reliabilities for different given demands of the SMN. Simulation experiments of different size were made and the system reliability precision was calculated. The precision of simulation results also discussed.     

Deterministic network interdiction optimization via an evolutionary approach

This paper introduces an evolutionary optimization approach that can be readily applied to solve deterministic network interdiction problems. The network interdiction problem solved considers the minimization of the maximum flow that can be transmitted between a source node and a sink node for a fixed network design when there is a limited amount of resources available to interdict network links. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link. For this problem, the solution approach developed is based on three steps that use: (1) Monte Carlo simulation, to generate potential network interdiction strategies, (2) Ford-Fulkerson algorithm for maximum s-t flow, to analyze strategies’ maximum source-sink flow and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate the approach. In terms of computational effort, the results illustrate that solutions are obtained from a significantly restricted solution search space. Finally, the authors discuss the need for a reliability perspective to network interdiction, so that solutions developed address more realistic scenarios of such problem.     

The k-out-of-n acyclic multistate-node networks reliability evaluation using the universal generating function method

In this article, a special node called the k⁻-out-of-n node, which cannot receive more than a certain amount of flows, is newly introduced. The acyclic multistate-node network (AMNN) that unsatisfied the flow conservation law is then extended to the k-out-of-n AMNN by including the k⁻-out-of-n and k⁺-out-of-n nodes. A very simple universal generating function method (UGFM) based on some intuitive properties that characterize the structure of the k-out-of-n AMNN is developed to solve the k-out-of-n AMNN reliability. The correctness of the proposed UGFM will be analyzed and proven. An example with three special cases illustrates how the k-out-of-n AMNN reliability is evaluated using the proposed UGFM. To show that the proposed UGFM can also solve the AMNN reliability, the first case of the example demonstrates that the proposed UGFM without needing to remove redundant terms and collecting like terms is more efficient and reasonable than the best-known UGFM.     

Reliability assessment for a stochastic manufacturing system with reworking actions

This article evaluates the system reliability of a manufacturing system with reworking actions, where the system reliability is an essential indicator to determine whether the manufacturing system is capable or not. Based on the path concept, we transformed the manufacturing system into a stochastic-flow network in which the capacity of each machine is stochastic (i.e., multistate) due to failure, partial failure, and maintenance. In such a manufacturing network, the input flow (raw materials/WIP; work-in-process) processed by each machine might be defective and thus the output flow (WIP/products) would be less than the input amount. To analyze the different sources processed by the manufacturing network, we decomposed the network into one general processing path and several reworking paths by a graphical technique. Subsequently, an algorithm for the manufacturing network was proposed to generate the lower boundary vector which allows sufficient products to satisfy the demand. In terms of such a vector, the system reliability can be derived easily.     

Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies’ source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.     

System reliability of a manufacturing network with reworking action and different failure rates

From the perspective of network analysis, the manufacturing system can be constructed as a stochastic-flow network, since the capacity of each machine is stochastic (i.e. multistate) owing to the failure, partial failure, and maintenance. Considering reworking action and different failure rates of machines, the input flow (raw materials/work in process) processed by each machine might be defective, and therefore the output flow (work in process/products) would be less than the input amount. To evaluate the capability of the manufacturing system, we measure the probability that the manufacturing network can satisfy demand. Such a probability is defined as the system reliability. A decomposition method is first proposed to divide the manufacturing network into one general processing path and one reworking path. Subsequently, two algorithms are utilised for different network models to generate the lower boundary vector of machine capacity to guarantee that the manufacturing network is able to produce sufficient products fulfilling the demand. The system reliability of the manufacturing network can be derived in terms of such a capacity vector afterwards.     

A path-based algorithm for evaluating the k-out-of-n flow network reliability

Evaluating the network reliability is an important topic in the planning, designing and control of systems. The minimal path (MP, an edge set) set is one of the major, fundamental tools for evaluating network reliability. A k-out-of-n MP is a union of some MPs in a k-out-of-n flow network in which some nodes must receive flows from their k input distinctive edges (each input edge has one flow) to generate one flow, where k is an integer number between 2 and n. In this study, a very simple a-lgorithm based on some intuitive theorems that characterize the k-out-of-n MP structure and the relationship between k-out-of-n MPs and k-out-of-n MP candidates is developed to solve the k-out-of-n flow network reliability by finding the k-out-of-n MPs between two special nodes. The proposed algorithm is easier to understand and implement. The correctness of the proposed algorithm will be analyzed and proven. One example is illustrated to show how all k-out-of-n MPs are generated and verified in a k-out-of-n flow network using the proposed algorithm. The reliability of one example is then computing using the same example.     

Confidence bounds for the reliability of binary capacitated two-terminal networks

Binary capacitated two-terminal reliability at demand level d (2TR_d) is defined as the probability that network capacity, generated by binary capacitated components, between specified source and sink nodes is greater than or equal to a demand of d units. For the components that comprise these networks, reliability estimates are usually obtained from some source of testing. For these estimates and depending on the type of testing, there is an associated uncertainty that can significantly affect the overall estimation of 2TR_d. That is, an accurate estimate of 2TR_d is highly dependent on the uncertainty associated to the reliability of the network components. Current methods for the estimation of network reliability and associated uncertainty are restricted to the case where the network follows a series-parallel architecture and the components are binary and non-capacitated. For different capacitated network designs, an estimate on 2TR_d can only be approximated for specific scenarios. This paper presents a bounding approach for 2TR_d by explaining how component reliability and associated uncertainty impact estimates at the network level. The proposed method is based on a structured approach that generates a α-level confidence interval (CI) for binary capacitated two-terminal network reliability. Simulation results on different test networks show that the proposed methods can be used to develop very accurate bounds of two-terminal network reliability.     

Minimal cut sets of s–t networks with k-out-of-n nodes

In this paper, we extend traditional directed s–t network by letting nodes have k-out-of-n property: To generate output flows, a node must receive at least k flows from its n input links, where k is an integer assigned for the node and its value can be any number from 1 to n. To evaluate the system reliability, minimal cut sets for the extended network are defined for nodes. Under this definition, an extended network and its sink node have the same minimal cut sets. A new algorithm is designed to generate minimal cut sets for all nodes, starting with the source node and ending with the sink node. With different initializations, the algorithm can be applied for extended s–t networks with or without node failures.     

Reliability of a Multi‐State Computer Network Through k Minimal Paths Within Tolerable Error Rate and Time Threshold

A computer system is usually modeled as a network topology where each branch denotes a transmission medium and each vertex represents a station of servers. Each branch has multiple capacities/states due to failure, partial failure, and maintenance. Such a network is named a multi‐state computer network (MSCN). From the viewpoint of quality management, transmission error rate and transmission time are both critical performance indicators to assess Internet quality for system managers and customers. Within both tolerable error rate and time threshold, the addressed problem is concentrated on an MSCN for computing the probability that d units of data can be sent through multiple minimal paths simultaneously. Such a probability is named system reliability. A solution procedure including an efficient algorithm based on MPs is proposed to derive the lower boundary vectors (LBVs) meeting the requirements. Then system reliability, which is represented as the probability of union of subsets, can be subsequently evaluated by the LBVs. Copyright © 2015 John Wiley & Sons, Ltd.     

A Genetic Algorithm to Solve Capacity Assignment Problem in a Flow Network

Computer networks and power transmission networks are treated as capacitated flow networks. A capacitated flow network may partially fail due to maintenance. Therefore, the capacity of each edge should be optimally assigned to face critical situations—i.e., to keep the network functioning normally in the case of failure at one or more edges. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. The RDP is known as NP-hard. Thus, capacity assignment problem subject to system reliability and total capacity constraints is studied in this paper. The problem is formulated mathematically, and a genetic algorithm is proposed to determine the optimal solution. The optimal solution found by the proposed algorithm is characterized by maximum reliability and minimum total capacity. Some numerical examples are presented to illustrate the efficiency of the proposed approach.     

Maximal network reliability for a stochastic power transmission network

Many studies regarded a power transmission network as a binary-state network and constructed it with several arcs and vertices to evaluate network reliability. In practice, the power transmission network should be stochastic because each arc (transmission line) combined with several physical lines is multistate. Network reliability is the probability that the network can transmit d units of electric power from a power plant (source) to a high voltage substation at a specific area (sink). This study focuses on searching for the optimal transmission line assignment to the power transmission network such that network reliability is maximized. A genetic algorithm based method integrating the minimal paths and the Recursive Sum of Disjoint Products is developed to solve this assignment problem. A real power transmission network is adopted to demonstrate the computational efficiency of the proposed method while comparing with the random solution generation approach.     

A simple algorithm for evaluating the k-out-of-n network reliability

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The minimal cut set (MC, an edge set) is one of the major and fundamental tools for evaluating network reliability. A k-out-of-n MC is a special MC in a k-out-of-n network in which some nodes must receive at least k flows from their n input edges, where k is an integer number between 1 and n. In this study, an alternative method is given first to define a MC using a node set (called MCN) in k-out-of-n networks. A very simple algorithm based on some intuitive theorems that characterize the structure of the MCN and the relationship between MC and MCN is developed to solve the k-out-of-n network reliability by finding the k-out-of-n MCs between two special nodes. The proposed algorithm is not only easier to understand and implement, but is also better than the existing algorithm. The correctness of the proposed algorithm will be analyzed and proven. Two examples are illustrated to show how all k-out-of-n MCs are generated and verified in a k-out-of-n network using the proposed algorithm. The reliability of one example is then computing using one example.     

Organizing distributed data bases for parallel searching

Abstract

This paper is mainly concerned with the problem of distributing a data base (i.e., a set of segments) in a computer network system so as to facilitate parallel searching. In our distributed data base model, we assume that all segments are stored in nodes. Each time a query occurs, all nodes are searched concurrently. For convenience, we define the time required to access a segment from any node as a time unit. For a network with d nodes, the response time of a query is then identical to the maximum (n ₁ , n ₂, …, n_d ), where n_i , is the number of segments that satisfies the query and is stored in node i. Unfortunately, the solution for finding an optimal way to organize a distributed data base for parallel searching is still at large. In other words, given a data base, there is no efficient polynomial time algorithm for finding an optimal arrangement of segments onto nodes. In this article, we shall present a “heuristic algorithm” based upon a multivariant analysis method in statistics to distribute a data base in a network system. Some experimental results will show that our method is indeed feasible and effective.     

Reliability evaluation of capacitated-flow networks with budget constraints

Many real-world systems such as transportation systems and manufacturing systems can be regarded as flow networks whose arcs have independent, finite and multi-valued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for level (d,c), i.e., the probability that d units of flow can be transmitted from the source node to the sink node such that the total transmission cost is less than or equal to c, can be computed in terms of minimal path vectors to level (d,c) (named (d,c)-MPs here). The main objective of this paper is to present a simple algorithm to generate all (d,c)-MPs of such a system for each level (d,c) in terms of minimal pathsets. Two examples are given to illustrate how all (d,c)-MPs are generated by our algorithm and then the reliability of one example is computed.