Optimal reliability enhancement for multi-state transmission networks with fixed transmission times

Multi-state acyclic transmission networks (MATNs) consist of a number of positions in which independent multi-state elements (MEs) capable of receiving and/or sending a signal are allocated. Each network has a root position where the signal source is located, a number of terminal positions that can only receive a signal, and a number of intermediate positions containing MEs that retransmit the received signal to some other positions. The signal propagation is allowed only in direction of the terminal nodes, which avoids cycles in the network. Each ME that is located in a nonterminal node can have different states determined by a set of nodes receiving the signal directly from this ME. The probability of each state is assumed to be known for each ME. The signal transmission process is associated with delays. The system fails if the signal generated at the first position (source) cannot reach the terminal nodes within a specified time. Rapid changes in digital network technology provides increase of transmission speed of communication lines. Replacement of old lines with the new high performance ones can considerably reduce the signal delivery time in MATN. Subject to budget limitations a question arises which lines should be replaced to obtain the desired reliability improvement effect. An algorithm for solving the minimal cost MATN enhancement problem subject to reliability constraint is presented in the paper. The algorithm is based on an extended universal generating function technique used for MATN reliability evaluation and on a genetic algorithm used as an optimization engine. © 2002 Published by Elsevier Science Ltd.