Magnitude Relation of the All-terminal Reliability of Network Systems
Volume 11, Number 4, July 2015 - Paper 4 - pp. 339-348
XIAO XIAO, Yi CHEN, NATSUMI TAKAHASHI, and HISASHI YAMAMOTODivision of Management Systems Engineering, Faculty of System Design, Tokyo Metropolitan University, 6-6 Asahigaoka, Hino, Tokyo 191-0065, JAPAN
(Received on August, 29, 2014, revised on December 15, 2014)
We concern the minimization problem of the total construction cost subject to the condition that the all-terminal reliability is not less than a reliability threshold. Although algorithm for solving this problem has been developed based on the so-called branch and bound method, it is known that the implement of the existing algorithm requires a fair amount of time, especially in the case that the number of edges is quite greater than the number of nodes. To reduce the computational time, we apply factoring method to classify network systems into several types (groups), and specify the type which has greater all-terminal reliability than the other types. Furthermore, we derive the exact maximum all-terminal reliability of the network systems with n+4 edges. Our proposal directly leads to a significant improvement of the overall efficiency of the optimization algorithm.
Click here to download the paper.
Please note : You will need Adobe Acrobat viewer to view the full articles.