Distribution of the Time Through a Directed, Acyclic Network

J. J. Martin
Additional contact information
J. J. Martin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1965, vol. 13, issue 1, 46-66

Abstract: Let there be associated with each arc of a directed, acyclic network a random variable, conveniently referred to as the arc passage time. It is assumed that the arc passage times are independent and have a finite range. A method is presented for the efficient computation of the density function of the passage time from source to sink of this network, under the restriction that the arc density functions are polynomials. In particular, an algorithm is described that reduces a series-parallel network to a single arc whose density function is that of the time through the original network. The specialization of this algorithm to the class of polynomial density functions leads to a detailed examination of the convolution operation for polynomials. Finally, a method is presented whereby any directed, acyclic network can be transformed to series-parallel form, permitting application of a modified version of the series-parallel algorithm. These techniques are used to find the probability that an arc is on the critical path and a numerical example is presented.

Date: 1965
References: Add references at CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.13.1.46 (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:13:y:1965:i:1:p:46-66

Access Statistics for this article

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