Improving efficiency of solving d-MC problem in stochastic-flow network

摘要

Solving d-MC problem is often a tedious process. Three ways are suggested to improve the efficiency of solving d-MC problem. The first way is to make the best use of some special properties of network. A property of Network with Joint Parallel Part, which is more common than series-parallel network, is illustrated. The second way is to reduce the number of d-MC candidates and then to reduce the cost of testing. Two theorems on how to find the d-MCs with only one element unsaturated and on how to set the Lower Capacity Limits (LCLs) of elements to some values higher than zero are proved. These two theorems will be helpful to reduce d-MC candidates without any loss of real d-MC. The third way is to efficiently remove the duplicated d-MCs. A theorem, elucidating which Minimal Cuts (MCs) the duplicated d-MCs will be generated from, is proved. Finally, an algorithm is proposed by adding a pre-numerating step to the algorithm presented in Yeh [A new approach to the d-MC problem. Reliab Eng Syst Safety 2002;77(2):201-6], and two examples are employed to illustrate the proposed algorithm, especially the pre-numerating step.