Multistate components assignment problem with optimal network reliability subject to assignment budget

Yi-Kuei Lin*, Cheng Ta Yeh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Scopus citations


The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component's failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.

Original languageEnglish
Pages (from-to)10074-10086
Number of pages13
JournalApplied Mathematics and Computation
Issue number24
StatePublished - 15 Aug 2011


  • Assignment budget
  • Genetic algorithm
  • Multistate components assignment
  • Optimal network reliability
  • State-space decomposition
  • Stochastic-flow network


Dive into the research topics of 'Multistate components assignment problem with optimal network reliability subject to assignment budget'. Together they form a unique fingerprint.

Cite this