ON THE COMPUTATIONAL-COMPLEXITY OF RELIABILITY REDUNDANCY ALLOCATION IN A SERIES SYSTEM

被引：384

作者：

CHERN, MS

机构：

[1] Department of Industrial Engineering, National Tsing Hua University, Hsinchu

来源：

OPERATIONS RESEARCH LETTERS | 1992年 / 11卷 / 05期

关键词：

RELIABILITY; REDUNDANCY OPTIMIZATION; KNAPSACK PROBLEM; NP-COMPLETENESS; NP-HARDNESS; GREEDY ALGORITHM;

D O I：

10.1016/0167-6377(92)90008-Q

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Finding the optimal redundancy that maximizes the system reliability is one of the important problems in reliability theory. A good deal of effort has been done in this field. In this paper, we prove that some reliability redundancy optimization problems are NP-hard. We also derive alternative proofs for the NP-hardness of some special cases of the knapsack problem.

引用

页码：309 / 315

页数：7

共 11 条

[1]

BARLOW RE, 1965, MATH THEORY RELIABIL

[2] PARAMETRIC PROGRAMMING APPLIED TO RELIABILITY OPTIMIZATION PROBLEMS [J].