A New Universal Generating Function Method for Solving the Single (d,tau)-Quick path Problem in Multi-state Flow Networks

Many real-world multistate systems, including distribution systems and supply chain management systems, can be modeled as multistate flow networks (MFNs). A single quickpath MFN (QMFN) is a special MFN with two characteristicsâ bandwidth and lead timeâin each arc. A (d, Ï )-quick path (i.e., (d, Ï )-QP) is also a special minimal path (MP) such that d units of data can be sent from the source node to the sink node within Ï units of time. The associated QMFN reliability problem evaluates the probability that a (d, Ï )-QP exists in a QMFN. All known algorithms for this reliability problem require the advance determination of all MPs, which is an NP-hard problem. A very straightforward and easily programmed algorithm derived from the universal generating function method (UGFM) is suggested to find all (d, Ï )-QPs prior to calculating the QMFN reliability, without the necessity of all MPs being known in advance. The correctness of the proposed UGFM is proven, and an analysis of its computational complexity indicates that it ismore efficient than known algorithms. An example is provided by way of illustration