Reliability analysis of a simple replicated and-fork/and-join graph

De Ron Liang, Rong Hong Jan

Research output: Contribution to journalArticlepeer-review


In this paper, we consider the problem of calculating the reliability of the replicated and-fork/and-join (RAFAJ) task graphs. An RAFAJ task graph is generated from an AFAJ task graph with vertex and arc replications. Due to the AFAJ constraint, the task graphs considered in our problem are more general than those considered in the network reliability problem, which is an NP-complete problem for general task graphs. In this paper, we propose an algorithm with time complexity O(n · 22r); where n is number of concurrent tasks, and r is the number of replications.

Original languageEnglish
Pages (from-to)51-59
Number of pages9
JournalOperations Research Letters
Issue number1
StatePublished - Aug 1994


  • Algorithms
  • Computational complexity
  • Fork-join graphs
  • Graph theory
  • Reliability


Dive into the research topics of 'Reliability analysis of a simple replicated and-fork/and-join graph'. Together they form a unique fingerprint.

Cite this