標題: RELIABILITY-ANALYSIS OF A SIMPLE REPLICATED AND-FORK AND-JOIN GRAPH
作者: LIANG, DR
JAN, RH
資訊工程學系
Department of Computer Science
關鍵字: GRAPH THEORY;FORK-JOIN GRAPHS;RELIABILITY;COMPUTATIONAL COMPLEXITY;ALGORITHMS
公開日期: 1-Aug-1994
摘要: 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 numbere of concurrent tasks, and r is the number of replications.
URI: http://hdl.handle.net/11536/2398
ISSN: 0167-6377
期刊: OPERATIONS RESEARCH LETTERS
Volume: 16
Issue: 1
起始頁: 51
結束頁: 59
Appears in Collections:Articles