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

De Ron Liang; Rong Hong Jan

doi:10.1016/0167-6377(94)90022-1

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

De Ron Liang, Rong Hong Jan

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

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 · 2^2r); where n is number of concurrent tasks, and r is the number of replications.

Original language	English
Pages (from-to)	51-59
Number of pages	9
Journal	Operations Research Letters
Volume	16
Issue number	1
DOIs	https://doi.org/10.1016/0167-6377(94)90022-1
State	Published - Aug 1994

Keywords

Algorithms
Computational complexity
Fork-join graphs
Graph theory
Reliability

Access to Document

10.1016/0167-6377(94)90022-1

Cite this

@article{88edf46840ca45839e29301d26dff60c,

title = "Reliability analysis of a simple replicated and-fork/and-join graph",

abstract = "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.",

keywords = "Algorithms, Computational complexity, Fork-join graphs, Graph theory, Reliability",

author = "Liang, {De Ron} and Jan, {Rong Hong}",

year = "1994",

month = aug,

doi = "10.1016/0167-6377(94)90022-1",

language = "???core.languages.en_GB???",

volume = "16",

pages = "51--59",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "1",

}

TY - JOUR

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

AU - Liang, De Ron

AU - Jan, Rong Hong

PY - 1994/8

Y1 - 1994/8

N2 - 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.

AB - 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.

KW - Algorithms

KW - Computational complexity

KW - Fork-join graphs

KW - Graph theory

KW - Reliability

UR - http://www.scopus.com/inward/record.url?scp=0028494120&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(94)90022-1

DO - 10.1016/0167-6377(94)90022-1

M3 - 期刊論文

AN - SCOPUS:0028494120

SN - 0167-6377

VL - 16

SP - 51

EP - 59

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this