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

IEEE Transactions on Systems, Man, and Cybernetics--Part A: Systems and Humans
Publication Type:
Journal Article
IEEE Transactions on Systems, Man and Cybernetics (Part A), 2012, 42 (6), pp. 1476 - 1484
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012001218OK.pdf264.58 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: