ISSN:0028-3045    

DOI:10.1002/net.3230250303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractThis paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. In each model, the arcs randomly and independently take on two possible states–an “operating” state and a “failed” state–corresponding to two different capacity/task‐time values, and the network is required to maintain a specified “threshold” max‐flow/project‐completion‐time value. In general, this problem is NP‐hard. We address the special case in which the difference between the lower and higher arc lengths is constant for every arc in the network. For these special cases, we show that if the underlying system is 1‐critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain the required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path or, equivalently, that the set of failed elements in a given partial order comprises achainin that order. We also show how the basic approach can be used to generate bounds for systems

ISSN:0028-3045    

DOI:10.1002/net.3230250304

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractWe examine a heuristic to approximate various reliability‐related parameters of communications networks under link failures. The heuristic is based on Monte Carlo and Markov chain simulation techniques. (These techniques have emerged in recent years in theoretical computer science in the context of obtaining efficient approximations forNP‐hard combinatorial optimization problems.) We present the ideas of these Monte Carlo and Markov chain techniques in terms of a specific reliability measure. The general method could be applicable to other reliability measures, just as it has been applied to other combinatorial problems. We present initial experimental results that suggest our approach is typically efficient in the computational complexity sense (running in time polynomial the size of the input); furthermore, our results suggest practical applicability for medium‐size networks and single‐edge parameters. As an example, we present the results of our experiments on a network that was posed for analysis by Applied Research at Bellcore: We estimated all single‐edge parameters on a single DEC‐5000 in less than 4 hours. The software that supported our experiments involves approximately 3000 lines of C code and is easy to adapt to other a

ISSN:0028-3045    

DOI:10.1002/net.3230250305

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractMany real‐world systems such as electric power transmission and distribution systems, transportation systems, and manufacturing systems can be regarded as flow networks whose arcs have independent, finite, and multivalued random capacities. Such a flow network is indeed a multistate system with multistate components and so its reliability for the system demandd, i.e., the probability that the maximal flow is no less thand, can be computed in terms of minimal path vectors to leveld(namedd‐MPs here). The main objective of this paper was to present a simple algorithm to generate alld‐MPs of such a system for each system capacity leveldin terms of minimal pathsets. Analysis of our algorithm and comparison to Xue's algorithm shows that our method has the following advantages: (1) the family ofd‐MP candidates that it generates is smaller in size and sod‐MPs can be generated more efficiently, (2) it is expressed more intuitively and so easier to understand, and (3) whenever applied in a series‐parallel case, both algorithms are essentially the same, but in a non series‐parallel case, Xue's algorithm needs the extra work to transform the system into a series‐parallel in advance. Two examples are illustrated to show how alld‐MPs are generated by our algorithm and then the reliability of one ex

ISSN:0028-3045    

DOI:10.1002/net.3230250306

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractThis paper characterizes a class

ISSN:0028-3045    

DOI:10.1002/net.3230250307

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractSeveral algorithms have been developed to solve the reliability problem for nonseries‐parallel networks using thesum of disjoint products (SDP)approach. This paper provides a general framework for most of these techniques. It reviews methods that help improve computer time and memory requirements in reliability computation. These parameters are generally used to compare SDP algorithms. We also overview three multiple variable inversion algorithms that result in sum of disjoint products expressions with fewer terms than that of algorithms that use only a single‐variable inversion. One common network is solved for two‐terminal network reliability using each of these algorithms. Finally, we have provided a comparison among these techn

ISSN:0028-3045    

DOI:10.1002/net.3230250308

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

摘要:

AbstractShanthikumar developed an upper bound for two‐terminal reliability based on consecutives – tcutsets. Subsequently, Shier generalized this strategy to obtain upper bounds from cutsets, and lower bounds from pathsets, when the cutsets or pathsets form a semilattice structure. We examine a restricted case of Shier's method that yields ak‐terminal lower bound based on consecutive pathsets. Our approach employs a common reduction of consecutive cut and path bounds to the computation of the two‐terminal reliability of an interval graph with imperfect vertices. Computational results are given to support the observation that the consecutive paths lower bound is competitive with the best efficiently computable bounds that are currently available. We then apply the consecutive path bound to reduce, in some cases dramatically, the number of states generated in a most probable state bounding

ISSN:0028-3045    

DOI:10.1002/net.3230250309

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230250302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1995

数据来源: WILEY