Title :
A New Universal Generating Function Method for Solving the Single
-Quick-Path Problem in Multistate Flow Networks
Author :
Yeh, Wei-Chang ; El Khadiri, Mohamed
Author_Institution :
Integration & Collaboration Lab., Univ. of Technol. Sydney, Sydney, NSW, Australia
Abstract :
Many real-world multistate systems, including distribution systems and supply chain management systems, can be modeled as multistate flow networks (MFNs). A single quick-path 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 is more efficient than known algorithms. An example is provided by way of illustration.
Keywords :
computational complexity; network theory (graphs); QMFN reliability problem; UGFM; computational complexity; distribution systems; multistate flow networks; quick-path MFN; real-world multistate systems; single (d, τ)-quick-path problem; supply chain management systems; universal generating function method; Algorithm design and analysis; Computational complexity; Random variables; Supply chain management; Telecommunication network reliability; $(d, tau)$-quick path; minimal path (MP); multistate flow network (MFN); network reliability; universal generating function method (UGFM);
Journal_Title :
Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on
DOI :
10.1109/TSMCA.2012.2190058