一种二元决策图底事件排序的新方法

17220084JournalofSystems&ManagementVol.17No.2Apr.2008:100522542(2008)0220210207,(,200052)(FaultTreeAnalysis,FTA),(BinaryDecisionDiagram,BDD)BDD,BDD,:,BDD,,BDD,,75%BDD:;;:N945.25;O231.5:AANovelOrderingMethodofBinaryDecisionDiagramSUNYan,DUSu2guo(AntaiCollegeofEconomics&Management,ShanghaiJiaotongUniversity,Shanghai200052,China)AbstractFaulttreeanalysis(FTA)hasbeenwidelyusedforquantitativeandqualitativeanalysisonthereliabilityofasystem.Anefficientwaytoanalyzeafaulttreeisbinarydecisiondiagram(BDD)method,whichcantakeadvantageofcomputertechnologytoautomaticallydealwithalargescalefaulttree.How2ever,inordertousethismethod,thefaulttreehastobeconvertedintoaBDDformatfirst.Duringtheconversionprocess,theevent2orderingproblemisakeyissueforagoodBDDsgeneration.Inthispaper,anovelorderingmethod,namedasneighbor2event2firstmethod,isproposed.Inthenewmethod,theor2derofthebasiceventvariablesisdeterminedbasedontheirrelevantpositiontoeachother.Themajorcharacteristicoftheneighbor2eventfirstmethodisthattheorderingprocessfollowsapre2definedwaywhileitcanalsoallowdifferentorderingstrategyinBDDbranches.ComparedwiththeexistingbestBDDorderingheuristics,theproposedschemecanachieveperformanceimprovementon75%oftestcases.Keywords:faulttreeanalysis(FTA);binarydecisiondiagram(BDD);variableorderingheuristics:2007203205:(70501019):(19822),,E2mail:[e-mail](FaultTreeAnalysis,FTA),[1],,,(BinaryDecisionDiagram,BDD)[2]BDD,,BDD,,BDD,BDD,BDD,BDD,,BDD,BDD,[3],,[4],,,[5],,,,BDD[6],BDD,,BDD,,BDD,BDD,,75%,1BDD1.1BDDBDDBDP(BinaryDecisionProgram),,,11BDD(1),,01,,0,1(1)Xi,XiFi,,Fi10(1)0,;1,1.2BDDBDD,BDD,BDD,BDD,,BDDBDD,,[4]BDDBDDv,10,vw,01,,BDD1,v,v;2,vw(v),vw,vBDD,BDD1.3BDDBDD,[7]:,,,,,:,:BDD,,BDD,,BDD,1122,:,BDD,22.1,,BDD,,,BDD,,,,BDD,,,,BDDBDD,,BDD[6],BDD,,BDD,2.22.2.1BDD,2:G1AG2,G2A;,G2BC,CB2:B,B,BBC,,,BDD,,:A3(A+B)=A(1)A+A3B=A(2),,,:(1),,;,;,;,,Ai(i=1,2,,n),,;,(2),,,;,;,,Ai(,,;,;,),(2)(3),(1),(1)(3),;,,,,,;,;,,Ai(,,21217;,;,),,(2)(3),(1),(1),,A1,A2,,An2.2.2BDDBDD,A1,A2,,An,,,,,BDD,1.2,BDD2.3(3)3,,G7e15,e15G7,e15+e15e9e6e4=e15G7,e9,e6,e4,e151,e7e11e1,A1,,e72,e112,e11,,e7e11,3A1(e7e11e1)2,G1G2e7e11e1,G1G2e7e11e1G5e7,G8e11,e7e11,e7e7A2,e7,e7,A2(e7e10)3e7e10,G5G2(,G5),G6e10e10e13A3(e10e13),e10e13,3,G6G2,,G21,1,e4e3e12,e4,A4(e4e3e12)A4G2,,G2TOP,e11e4,,A5(e11e4e14e5),e11e4e14e5,,A6(e0e8),A7(e15),BDDBDD44BDDBDD,(5)BDD,,,A1(e1);A2(a);A3(e2);A4(be5);A5(ae4);A6(be7);A7(e3)BDD,A1e1,e1,e11,,A2a;e10,G1,A2(a),3122,:A3(e2),A4(be5),A5(ae4)a,aBDD,BDD,BDD656BDD6:e1,,e1,be4;,e4bBDD,,,,e1ae2be5e4e7e3,BDD767,BDD7BDD33.1,,C83.2BDDBDD:(1),,,(2),,(3),,,(4),,(5),1;;,(6),,1/2,,:P=ni=1qi412178P=1-ni=1(1-qi),,,,(7),Birnbaums,BDD,,BDD3.3,3.23BDD,,e7e11e1e4e3e12e15e0e8e10e13e9e6e14e5,,BDD99BDD,3.23BDD1BDD,1,2,,71BDDBDD1e7e11e1e4e3e12e15e0e8e10e13e9e6e14e5132e7e11e1e4e3e12e15e10e0e8e13e9e6e14e5123e7e11e1e15e9e6e4e0e8e14e5e3e12e10e13134e7e11e1e15e4e9e6e0e8e14e5e3e12e10e13135e7e11e1e15e4e10e3e12e0e8e13e9e6e14e5146e7e11e1e0e8e4e14e5e15e3e12e10e13e9e6127e11e7e1e15e4e0e8e3e12e10e13e9e6e14e5131,3.2BDD,BDD12,,10Rauzy[4],BDD,BDD,BDD5122,:,BDD,BDD,,BDD40(A),,BDD3.2BDD(BDD,BDD),2402BDD³1025%3075%2,BDD3.2,,,BDD,BDD,BDD3.2,,,,BDD,,,,4BDD,BDD,BDD,,,BDD,,BDD,,,:BDD,,,,,BDD,,,,BDDA40BDDBDD1233=12711713244=2427107242543764036511747131610586109691824271041078111070219123961013266=3148161111155211112166161013171118131418950141519933161620101616=4211634161722418141823266=5241519151925821112026222=627139431212881713222983312233012171624311321152532277=733835142634388=835194727273612532928371521929381433233039101717=94071111=10(220)612172,:6,7,2;3,9,13,14;1,4,12;5,8,10,11:4,[4],:[1]MooreDL,FearonHE.Computer2assisteddecision2makinginpurchasing[J].JournalofPurchasing,1973,9(4):5225.[2].[J].,2003(5):49253.[3]GaballaAA.Minimumcostallocationoftenders[J].OperationalResearchQuarterly,1974,25(3):3892398.[4],.[J].,2003(3):93297.[5]GhodsypourSH,OBrienC.Adecisionsupportsys2temforsupplierselectionusinganintegratedanalytichierarchyprocessandlinearprogramming[J]IntJProductionEconomics,1998(56257):1992212.[6],.[M].:,1992,1362148.(216):[1].[M].:,2002.[2]BryantRE.Graph2basedalgorithmforbooleanfunc2tionmanipulation[J].IEEETrans,1986,35:6772691.[3]SinnamonRM,AndrewsJD.Newapproachestoevaluatingfaulttrees[J].QualityandReliabilityEn2gineeringInternational,1997,58:89296.[4]RauzyA.Newalgorithmsforfaulttreeanalysis[J].ReliabilityEngineeringandSystemSafety,1993,40:2032211.[5]BartlettLM,AndrewsJD.Anorderingheuristictodevelopthebinarydecisiondiagrambasedonstructuralimportance[J].ReliabilityEngineeringandSystemSafety,2001,72:31238.[6]BartlettLM,DuS.Newprogressivevariableorderingforbinarydecisiondiagramanalysisoffaulttrees[J].QualityandReliabilityEngineeringInternational,2005,21:4132425.[7]BartlettLM,AndrewsJD.Comparisonoftwonewapproachestovariableorderingforbinarydecisiondia2grams[J].QualityandReliabilityEngineeringInterna2tional,2001,17:1512158.[8],.[J].,1997,