Disjoint Products and Efficient Computation of Reliability

Michael O. Ball and J. Scott Provan
Additional contact information
Michael O. Ball: University of Maryland, College Park, Maryland
J. Scott Provan: University of North Carolina, Chapel Hill, North Carolina

Operations Research, 1988, vol. 36, issue 5, 703-715

Abstract: In this paper, we analyze the problem of computing the probability of the union of a set of events, where each event is given as the product of a set of Boolean variables. Each Boolean variable represents the operation or failure of a particular component. The problem has direct applications to the reliability analysis of complex systems as well as more general applications. After showing that the problem is NP-hard in general, we define simple, computationally efficient procedures for generating upper and lower bounds on the required probability. We show that these procedures produce the exact answer, i.e., the upper bound equals the lower bounds, for two classes of systems, matroids and threshold systems. These results draw on the relationship between this problem and the notion of shellability studied in the context of simplicial polytopes. Shellability is shown to have a very interesting and useful interpretation in this problem setting.

Keywords: mathematics: combinatorics; networks/graphs; stochastic; reliability (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.5.703 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:36:y:1988:i:5:p:703-715

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().