A dynamic bounding algorithm for approximating multi-state two-terminal reliability |
| |
Authors: | Chin-Chia Jane Yih-Wenn Laih |
| |
Affiliation: | 1. Department of Information Management, Ling Tung University 1, Ling Tung Road, Taichung 40816, Taiwan, ROC;2. Department of Finance, Ling Tung University 1, Ling Tung Road, Taichung 40816, Taiwan, ROC |
| |
Abstract: | This paper modifies Jane and Laih’s (2008) exact and direct algorithm to provide sequences of upper bounds and lower bounds that converge to the NP-hard multi-state two-terminal reliability. Advantages of the modified algorithm include (1) it does not require a priori the lower and/or upper boundary points of the network, (2) it derives a series of increasing lower bounds and a series of decreasing upper bounds simultaneously, guaranteed to enclose the exact reliability value, and (3) trade-off between accuracy and execution time can be made to ensure an exact difference between the upper and lower bounds within an acceptable time. Examples are analyzed to illustrate the bounding algorithm, and to compare the bounding algorithm with existing algorithms. Computational experiments on a large network are conducted to realize the performance of the bounding algorithm. |
| |
Keywords: | Reliability Multi-state network Network flow Upper/lower bounds |
本文献已被 ScienceDirect 等数据库收录! |
|