THRESHOLD RELIABILITY OF NETWORKS WITH SMALL FAILURE SETS

This paper addresses two classes of reliability analysis models: a net work flow model and a project scheduling model. In each model, the arc s randomly and independently take on two possible states-an ''operatin g'' state and a ''failed'' state-corresponding to two different capaci ty/task-time values, and the network is required to maintain a specifi ed ''threshold'' max-flow/project-completion-time value. In general, t his problem is NP-hard. We address the special case in which the diffe rence between the lower and higher are lengths is constant for every a re in the network. For these special cases, we show that if the underl ying system is 1-critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain t he required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by redu cing the problems to the problem of determining the probability that t he failed arcs in a directed acyclic graph lie on a single path or, eq uivalently, that the set of failed elements in a given partial order c omprises a chain in that order. We also show how the basic approach ca n be used to generate bounds for systems that are ''almost critical.'' (C) 1995 John Wiley and Sons, Inc.