Efficiently Estimating Survival Signature and Two-Terminal Reliability of Heterogeneous Networks through Multi-Objective Optimization

<p>The two-terminal reliability problem is a classical reliability problem with applications in wired and wireless communication networks, electronic circuit design, computer networks, and electrical power distribution, among other systems. However, the two-terminal reliability problem is among the hardest combinatorial problems and is intractable for large, complex networks. Several exact methods to solve the two-terminal reliability problem have been proposed since the 1960s, but they have exponential time complexity in general. Hence, practical studies involving large network-type systems resort to approximation methods to estimate the system's reliability. One attractive approach for quantifying the reliability of complex systems is to use signatures, but even signature-based approaches in computing exact network reliability may become computationally prohibitive as the number of components grows, and simulation-based approximations, such as Monte Carlo algorithms, are generally required. Nonetheless, the computation of the network's signature poses a majorchallenge in terms of computational time, especially when considering large, heterogeneous networks. Motivated by this, we propose a MC-survival signature based method to estimate two-terminal reliability for heterogeneous networks through multi-objective optimization. We formulate the problem of estimating the multi-dimensional survival signature of a network with heterogeneous components as a repeated multi-objective maximum capacity path problem and we present a fast and memory-efficient, Dijkstra-like algorithm to solve it. To the best of our knowledge, this is the first work to point out the relationship between the multi-dimensional survival signature computation and a multi-objective optimization problem. We empirically validate our method and perform computational experiments to compare its performance against two other approaches. The results of the experiments shows that our method is much faster than the other two approaches and can be used with a larger number of replications so to improve the accuracy of the reliability estimation. </p>

Name thesis:degree_name

Master of Science in Industrial Engineering (MSIE)

Level thesis:degree_level

Thesis

Year dc:date.available

2021

Author dc:creator

• Lopes da Silva, Daniel Bruno

Advisor dc:contributor.advisor

• Sullivan, Kelly M.

Contributors dc:contributor

• Eksioglu, Burak
• Liao, Haitao

• Bi-objective Dijkstra
• Monte Carlo estimation
• Multi-objective optimization
• Network optimization
• Reliability
• Survival signature
• Electrical and Electronics
• Industrial Engineering
• Industrial Technology
• Operational Research
• Signal Processing
• Systems and Communications
• Systems Engineering

Repository record dc:identifier

https://scholarworks.uark.edu/etd/4191

OAI identifier oai:identifier

oai:scholarworks.uark.edu:etd-5741