Using minimal cuts to optimize network reliability for a stochastic computer network subject to assignment budget

摘要

In our modern society, information and data are usually transmitted through a computer network. Since the computer network's reliability has a great impact on the quality of data transmission, many organizations devote to evaluating or improving network reliability, especially for network reliability optimization. This study focuses on such a confronted problem that is to find the optimal transmission line assignment to the computer network such that network reliability is maximized subject to the budget constraint. Each transmission line owns several states due to failure, maintenance, etc., and thus the computer network associated with any transmission line assignment is called a stochastic computer network. Network reliability is the probability that the computer network can transmit the specified units of data successfully. Because the discussed problem is NP-hard, an optimization algorithm that integrates the genetic algorithm, minimal cuts and Recursive Sum of Disjoint Products is proposed. Experimental results illustrate the solution procedure and show that the proposed algorithm can be executed in a reasonable time.