并行系统中排列图的可靠性近似算法  

Approximation Algorithm of Arrangement Graph Reliability in Parallel System

作　　者：于中宝 邵方明[1] YU Zhongbao;SHAO Fangming(Department of Mathematics,East China University of Science and Technology,Shanghai 200237,China)

机构地区：[1]华东理工大学数学系,上海200237

出　　处：《华东理工大学学报（自然科学版）》2020年第6期838-842,共5页Journal of East China University of Science and Technology

摘　　要：讨论了排列图子图可靠性界的鲁棒性问题和可靠性的近似算法,并构造了排列图的蒙特卡罗算法。仿真结果说明所构造的蒙特卡罗算法远优于已知的近似算法,A3,2子图可靠性的蒙特卡罗近似计算误差小于1%。In parallel system,the arrangement graph An,k has good properties such as symmetry,small diameter,and high fault tolerance.Subsystem reliability is defined as the probability that there is still a normal operating subsystem when the system has faults.It is usually used to measure the system health status,and the calculation of subsystem reliability is an NP-hard problem.This paper discusses the robustness of the reliability of the subgraphs and the approximate algorithm of reliability.Further,the Monte Carlo algorithm for arrangement graphs is constructed.The simulation results show that the constructed Monte Carlo algorithm is much better than the known approximation algorithm.In particular,the error of Monte Carlo approximation of A3,2 subgraph reliability is less than 1%.

关 键 词：可靠性 排列图 并行系统 近似算法 蒙特卡罗 

分 类 号：O29[理学—应用数学]