EuropeanJournalofOperationalResearchjournalhomepage:www.elsevier.com/locate/ejorExactandheuristicmethodsfortheselectivemaintenanceproblem
T.Lusta,O.Rouxb,*,F.RianebabFacultéPolytechniquedeMons,LaboratoryofMathematicsandOperationalResearch,9,ruedeHoudain,7000Mons,BelgiumFacultésUniversitairesCatholiquesdeMons,CentreofResearchandStudiesinIndustrialManagement,CatholicUniversityofMons,151,chausséedeBinche,7000Mons,Belgiumarticleinfoabstract
Wepresentinthispaper,newresolutionmethodsfortheselectivemaintenanceproblem.Thisproblemconsistsinfindingthebestchoiceofmaintenanceactionstobeperformedonamulticomponentsystem,soastomaximizethesystemreliability,withinatimewindowofalimitedduration.Whenthenumberofcomponentsofthesystemisimportant,thiscombinatorialproblemisnoteasytosolve,inparticularbecauseofthenonlinearobjectivefunctionmodelingthesystemreliability.Thisproblemdidnotreceivemuchattentionyet.Consequently,rarearetheeffectiveresolutionmethodsthatareofferedtotheuser.Wethusdevelopedheuristicsandanexactmethodbasedonabranchandboundprocedure,whichweapplytovarioussystemconfigurations.Wecomparetheobtainedresults,andweevaluatethebestmethodtobeusedinvarioussituations.Ó2008ElsevierB.V.Allrightsreserved.Articlehistory:Availableonline10April2008Keywords:SelectivemaintenanceReliabilityCombinatorialoptimizationBranchandboundTabusearch1.IntroductionInthispaper,weareinterestedinpreventivemaintenance[1–4],andmoreparticularlyintheselectivemaintenanceproblemthatcon-sistsinfindingthebestchoiceofmaintenanceactionstobeperformedonamulticomponentsystem,withinafixedtimewindow.Thislimitedtimedoesnotallowtocarryoutallmaintenanceactions.Theideaisthentopickoutasubsetofactionstoundertakewhosetotalexecutiondurationfitsinthetimewindowandthatyieldsmaximumreliabilitywhenthesystemisrestartedafterthemaintenanceperiod.Thiskindofproblemcanbeencounteredforequipmentthatperformssequencesofmissionsandcanberepairedonlybetweenmis-sions.Thisisthecaseformilitaryequipment,productionequipmentonwhichmaintenanceactionsarecarriedouttheweekend,vehiclesmaintainedbetweentwodeliveries,etc.ThisproblemhasbeenintroducedbyRiceetal.[5],wheretheyconsidersystemspresentingaparticulararchitecture,constantcomponentsfailureprobabilitiesandonlyonetypeofmaintenanceactions(torepairacomponent).Cassadyetal.[6]extendedthemodelofthisproblem,byconsideringcomponentsfailureprobabilitiesdependentontheirageandmul-tiplemaintenanceactions.Theysolvethisproblemforsystemsofspecificconfigurationbyasimpleenumerationofallpossiblesolutions.Thisenumerationgivesthesolutionforonlysmallsizesystems.Wethusproposenewresolutionapproaches:aconstructionheuristic,whichmakesitpossibletofindagoodsolutionveryquickly,atabusearchbasedmetaheuristic,whichallowstoimprovethequalityofthesolutionobtainedbytheconstructionheuristic(butalwayswithoutguaranteeofoptimality)andanexactmethod,basedonabranchandboundprocedureforbenchmarkingpurposes.Thispaperisorganizedinthefollowingway:weinitiallypresenttheselectivemaintenanceproblemtakenintoaccountanditsmod-eling.Wethendescribethenewresolutionmethodsdevelopedandthenumericalresultsofthesemethodsonvarioussystems.2.Selectivemaintenanceproblem’sstatementWedefineinthissectionthetypeofsystemthatweproposetostudy,thevarioustypesofmaintenanceactionsconsidered,andtheireffectsonthesystem.Wealsopresentthecalculationofthereliabilityofasysteminseriesand/orparallel.Weconsiderthatmaintenanceactionsarecarriedoutonasystem,havingtoaccomplishagivenmission,anddefinedbyasetofcom-ponentsconnectedtoeachotherinseriesand/orparallel.AnexampleofsuchasystemispresentedinFig.1.Inthisrepresentation,theblockscorrespondtothecomponents.Thefailureofoneofthecomponents3,4,5or10placedinseriesinvolvesthesystemfailure.Com-ponents6,7,8or9beingplacedinparallel,thesystemfailsonlyifthetwopartsoftheparallelsubsystemarenotfunctioning.Thisarriveswhenthefailureofoneofthecomponents6or7isincombinationwiththefailureofoneofthecomponents8or9.*Correspondingauthor.Fax:+3265323363.E-mailaddress:roux@fucam.ac.be(O.Roux).0377-2217/$-seefrontmatterÓ2008ElsevierB.V.Allrightsreserved.doi:10.1016/j.ejor.2008.03.047T.Lustetal./EuropeanJournalofOperationalResearch197(2009)1166–11771167Fig.1.Exampleofmulticomponentsystem.Thesystemmustperformasequenceofmissionswithbreaksofknownlengthbetweeneachmission,whenthemaintenanceactionscanbeaccomplished.Duringeachmission,componentscanfail.Consequently,attheendofamission,thecomponentsareeitherinoper-atingconditionorfailed.AsCassadyetal.[6],weconsidertwopossiblemaintenanceactionsduringthebreak:toreplace(bynew)afailedorafunctioningcomponent(thecomponentageaftertheactionisthusassumedtobeto0),tominimallyrepairafailedcomponent,whatrestartsthecomponent(thecomponentageaftertheactionisthusunchanged).Itshouldbenotedthatthesystemcanfailbeforeaprogrammedmaintenancebreak.Inthiscase,onlyminimalrepairsonthecompo-nentsthatcausedthebreakdownofthesystemwillbecarriedout,soastoputbackthesysteminoperatingcondition.Ifmanybreakdownsofthesystemoccurbeforethemaintenanceperiod,itshouldbeworthrevisingtheperiodicityofthemaintenanceactivitiesandthesystemdesign[7].Onceamaintenancebreakisstarted,theproblemistoselectasubsetofactionstobeperformedatthefixedperiodofthebreakinordertomaximizethesystemreliabilitywhileensuringtherespectofthelimiteddurationofthemaintenancebreak.Itistheproblemofreli-abilitymaximizationundertimeconstraint.Giventhatthecostofthemaintenanceactionsisconsiderednegligiblecomparedtothecostofastopofthesystemduringamission,wedonottakeintoaccountthecostsofthemaintenanceactionsinthemodelingoftheproblem.Wethusseekthemaintenanceactionsthatmakeitpossibletomaximizethesystemreliability,withoutconstraintofbudget.Weconsiderthatthecomponentfailureprobabilityforagivenmissionisdependentonitsage,i.e.thehigherthecomponentageis,thehigheritsfailureprobabilityis.Thisprobabilityismodeledthroughareliabilitylaw[8,9],themostusedprobabilitylawinmaintenanceistheWeibulldistribution.Thankstothecomponentsfailureprobabilities,wecandeterminethefunctioningprobabilityofthesystemforamis-sionofagivenduration,whichdependsonthefunctioningprobabilitiesofthecomponentsandonthesystemarchitecture.Contrarytopre-cedingmodelingsoftheselectivemaintenanceproblem[5,6],weconsiderinthispapergeneralsystemsinaseriesand/orparallelarchitecture.WepresentbelowthewaytocomputethefunctioningprobabilityofacomponentthankstoitsreliabilitylawoftheWeibulltype,andthefunctioningprobabilityofasystemaccordingtothefunctioningprobabilitiesofthecomponentsthatcomposeit.2.1.FunctioningprobabilityofacomponentThereliabilitylawgivestheprobabilitythatonecomponentachieveswithoutfailureamissionoflengtht.InthecaseoftheWeibulldistribution,theprobabilityRðtÞisgivenbythefollowingrelation:RðtÞ¼eÀðgÞ;wherebandgrepresent,respectively,theshapeandscaleparametersoftheWeibulldistribution.Theyarerealnumbersgreaterthanzero.IfthecomponentalreadycarriedoutamissionoflengthTandisinaoperatingconditionattheendofthismission,weuseconditionalreli-abilitytodeterminetheprobabilitythatthecomponentsuccessfullyachievesanewmissionoflengtht,definedbythefollowingrelation:TþtRðTþtÞeÀðgÞRðT;tÞ¼¼b:RðTÞÀðTÞgebtbWehaverepresentedinFig.2thecomparisonofthereliabilitylawofanewcomponentwiththatofacomponent30unitsoftimeaged,alwayswiththeWeibulllawðb¼4;g¼150Þ.Wecannoticethatthefunctioningprobabilitiesoftheoldcompoundarelowerthanthoseofthenewcomponent.Hence,startingfromthecomponentageandthemissionduration,itiseasy,inthecaseofareliabilitylawoftheWeibulltype,todeter-minetheprobabilitythatthecomponentachievesthemission.2.2.FunctioningprobabilityofamulticomponentsystemWecanconsideramulticomponentsystemasasetofsubsystemsentirelyinseriesorparallel.ThedecompositionofthesystemshowninFig.1isgiveninFig.3.Wehavesubsystem1inseriescomposedofcomponents6and7(SS1),subsystem2inseriescomposedofcom-ponents8and9(SS2)andsubsystem3inparallelcomposedofsubsystems1and2(SS3).Theglobalmulticomponentsystem(SG)inseriesisthuscomposedofcomponents3,4,5,10andsubsystem3.Byusingthisdecomposition,itisonlynecessarytodeterminethefunctioningprobabilitiesofsystemsentirelyinseries,orfunctioningprobabilitiesofsystemsentirelyinparallel.2.2.1.SysteminseriesInorderthatasysteminseriesfunctionsafteramissionofdurationt,itisnecessarythatallthecomponentsiofthesystemfunction.TheprobabilityRSðtÞthatthesystemfunctionsafteramissionofdurationtisthusequaltotheproductofthefunctioningprobabilitiesofthencomponentsthatcomposeit:RSðtÞ¼nYiRiðtÞ:1168T.Lustetal./EuropeanJournalofOperationalResearch197(2009)1166–11771NewAge=30 0.8Probability 0.6 0.4 0.200 50 100 150t 200 250 300Fig.2.ComparisonofthereliabilitylawoftheWeibulltypeðb¼4;g¼150Þforanewcomponentandacomponent30u.t.aged.Fig.3.Exampleofdecomposedmulticomponentsystem.2.2.2.SysteminparallelSothatasysteminparallelfunctionsafteramissionofdurationt,itisnecessarythatatleastonecomponentofthesystemfunctions.Astheprobabilitythatacomponentifailsisequaltoð1ÀRiðtÞÞ,theprobabilityRPðtÞthatthesystemfunctionsafteramissionofdurationtisequaltothecomplementwith1oftheproductofthefailureprobabilitiesofthencomponentsthatcomposeit:nYRPðtÞ¼1Àð1ÀRiðtÞÞ:i3.ProblemmodelingThemodelingoftheselectivemaintenanceproblemhasalreadybeenapproachedbyCassadyetal.[6].Weagainpartlytakethismod-elingbyextendingittoanysystemsinseriesand/orparallel.Weindicateby,respectively,tmri;triandtrfithetimesnecessarytocarryoutaminimalrepaironafailedcomponenti,toreplaceafailedcomponentiandtoreplaceafunctioningcomponenti.Wesupposethattmri SymbolsandconfigurationofthesystemsgeneratedSystem48*8+12*12+16*16+20*20+24*24+28*28+ConfigurationEE*EE+EE*(E+E)E+(E*E)E*(E+(E*E))E+(E*(E+E))E*(E+(E*(E+E)))E+(E*(E+(E*E)))E*(E+(E*(E+(E*E))))E+(E*(E+(E*(E+E))))E*(E+(E*(E+(E*(E+E)))))E+(E*(E+(E*(E+(E*E)))))T.Lustetal./EuropeanJournalofOperationalResearch197(2009)1166–1177Table3 ResultsoftheexactmethodsofresolutionoftheselectivemaintenanceproblemSystemsT0ðkÞ(h)OptimalreliabilityTimeoftheexactmethods(second)DFBB48*8+12*12+16*16+20*20+24*24+28*28+61212181824243030363642420.8740.7840.9870.9180.9830.9250.9940.9490.9950.9540.9970.9570.99800.010.010.050.071.510.5629.8118.22423.59237.487765.173483.51BFBB0000.050.040.880.49125.6568.47––––1175Enumeration00.020.020.830.7837.9237.621893.091727.905736055920––ThecomponentscharacteristicsofthissystemaregiveninTable1.Wecannoticethattwoofthefourcomponentsarefailedattheendofmissionk.Thefailureofthesecomponentsinvolvesthefailureofthesystem,sincethecomponent6inseriesisfailed.Theproblemthusconsistsinfindingthemaintenanceactionstobeundertakenduringthemaintenancebreaksoastomaximizethesystemreliabilityforthenextmission.Togeneratemorecomplexsystems,wetakeagaintheelementarysystem,whichismultipliedbyarrangingitinseriesand/orparallel.Theserializationisrepresentedbythesymbol*,andtheparallelizationbythesymbol+.Forexample,thesystem(E+E)*E(seeFig.6)iscomposedoftwoelementarysystemsputinparallel,thewholeputinserieswithanotherelementarysystem.So,thissystemiscomposedof12components,including6failedcomponents.Wehaveonthewholegenerated13systemsofdimensiongoingfromn¼4ton¼28.Thesymbolsusedfortherepresentationofthesesystems(whichalsoindicatesthenumberofcomponentsofthesystems)astheircon-figurationaregiveninTable2.ThedurationofthenextmissionLðkþ1Þisfixedat40daysforallthesystemsconsidered.ThemaintenancebreakT0ðkÞincreasesaccordingtothecomplexityofthesystem(themoretherearefailedcomponents,themoreweattributeamaintenancebreakofhighduration).5.2.ResultsoftheexactmethodsTheresultsoftheapplicationoftheexactmethods(DepthFirstBranch&Bound,BestFirstBranch&Boundandtheenumeration)forthevarioussystemsgeneratedstartingfromtheelementarysystemaregiveninTable3.Theywereobtainedona2.4GHzPentiumIVhaving480Moofmemory.Table4 ResultsoftheheuristicsofresolutionoftheselectivemaintenanceproblemSystems20*20+24*24+28*28+ConstructionheuristicReliability0.9240.9610.9240.9610.9240.961Gap(%)2.633.423.143.613.453.71Time(second)00.010.010.010.010.02TabusearchReliability0.9490.9940.9530.9950.9550.998Gap(%)00.100.100.200.210Time(second)0.5810.5810.8210.8411.1021.122 1.2DFBBTabu search1 0.8Reliability 0.6 0.4 0.200 20 40To 60 80 100Fig.7.ComparisonbetweentheDFBBandthetabusearchforthesystemnoted28*andforvariousdurationofthemaintenancebreakT0.1176T.Lustetal./EuropeanJournalofOperationalResearch197(2009)1166–1177 1.2DFBBConstruction Heuristic1 0.8Reliability 0.6 0.4 0.200 10 20 30 40 50 60ToFig.8.ComparisonbetweentheDFBBandtheconstructionheuristicforthesystemnoted28*andforvariousdurationofthemaintenancebreakT0.WeremarkthattheBFBBversionisfasterthantheDFBB,forsystemsofsizelowerorequalton¼16.Ontheotherhand,thisdifferenceintheexecutiontimeisnotverysignificant.Beyondn¼20,theDFBBbecomesfasterthantheBFBB,whatcanbeexplainedbythegreatmemoryplacerequestedbytheBFBB,whichisnecessarytothememorizationofallthenodesofthestructuretreethatarebeingexplored.Fromn¼24,thememoryplacerequestedbytheBFBBissuchasthemethodisnotmoreapplicable.Thecompleteenumerationoftheacceptablesolutionsquicklybecomesnotexploitableforsystemsofdimensiongreaterthann¼16.Indeed,forn¼20,theexecutiontimeisofapproximately30minutes,andforn¼24thistimebecomesequaltoapproximately15h.WealsonoticethattheresolutiontimeoftheDFBBstartingfrom20componentsdoesnotbecomenegligibleanymoreandthatitcanbeinter-estingtoapplyheuristicsifthesystemincludesatleast20components.5.3.ResultsoftheheuristicsWecompareinthissectiontheperformancesoftheconstructionheuristicandthetabusearchandweevaluatethegapbetweenthereliabilitiesobtainedbythesemethodsandtheoptimalreliability.Thenumberofiterationsofthetabusearchhasbeenfixedat1000giventhatnomoresignificantimprovementshavebeennotedbeyondthisnumber.Thesizeofthetabulistisfixedat7,andtheneighborhoodiscompletelyexplored,whichmakesthetabusearchdeterministic.Thus,onlyoneexecutionofthetabusearchisrealized.TheresultsoftheconstructionheuristicandthetabusearcharegiveninTable4,forthesystemshavingatleast20components,sinceithasbeenshownthatstartingfromthissize,itispreferabletoapplyheuristicsratherthananexactmethod.Wenotethattheresultsoftheconstructionheuristicarerelativelygood,sincethemaximumgapcomparedtotheoptimalsolutionis3.71%.Theexecutiontimeoftheheuristicismoreoververylow,whichmakesitpossibletoinstantaneouslyobtainthesolution.Thetabusearchmakesitpossibletoimprovetheresultsoftheheuristicandtobeveryclosetotheoptimalsolutions.Themaximumgapisindeed0.21%andtheexecutiontimeisofaboutonesecond.WealsorepresentinFig.7theevolutionofthereliabilityobtainedbythetabusearchcomparedtothereliabilityobtainedbytheDFBBaccordingtothedurationT0ofthemaintenancebreak.Weusedthesystemnoted28*.WeremarkthatwhateverthedurationT0,thereli-abilityofthetabusearchispracticallyequaltothereliabilityobtainedbytheexactmethod.InFig.8,werepresenttheevolutionofthereliabilityobtainedbytheconstructionheuristiccomparedtothereliabilityobtainedbytheDFBB.Wenotethattheresultsoftheheuristicarealsoveryclosetotheoptimalreliability(exceptforthemaintenancebreakT¼4wheretheconstructionheuristicobtainsareliabilityequalto0whereasoptimalreliabilityisequalto0.42).6.ConclusionWeproposedinthispapernewresolutionmethodsfortheselectivemaintenanceproblem,extendedtogeneralarchitecturesystemsinseriesand/orparallel.Wehighlightedthattheconstructionheuristicgivesgoodresults,andmoreoververyquickly.Theexactmethodsthathavebeendeveloped,basedonabranchandboundprocedure,makeitpossibletoconsiderablyreducetheexecutiontimeofacompleteenumerationofCassadyetal.[6].Thecomputationaltimeoftheexactmethodsbasedonthebranchandboundbecomes,however,impor-tantstartingfromn¼20,andweshowedthattheuseofmetaheuristics,suchasthetabusearch,madeitpossibletosignificantlyimprovetheresultsoftheconstructionheuristicandtoreachresultsveryclosetotheoptimalsolutionsinatimeremainingcompletelyacceptable.Theseresolutionmethodscouldbeatthebaseofanewstrategyofmaintenanceofmulticomponentsystems.ThisstrategywouldtakethedurationT0ofthemaintenancebreakandtheperiodTatwhichthesystemisstoppedasparameters.ItwouldthusprovenecessarytodeterminetheoptimaldurationT0(ifT0istooshort,fewmaintenanceactionscouldhavebeenundertakenandthesystemwillpresentfewchancestoachievethenextmissionandifT0istoohigh,theunavailabilityofthesystemwillincrease)andtheoptimalperiodT(ifthisperiodistoolong,thesystemislikelytofail).Forthis,amodelofsimulationshouldbedeveloped(reproducingthedynamicofthesystemduringthemissions),aswellasoptimizationmethodsforcontinuousproblems(todeterminethecontinuousparametersTandT0).Themethodsdevelopedinthispaperwouldinterveneatthetimeofthemaintenancebreak,forthedeterminationofthemaintenanceactionstobeundertaken.Otheractions,suchasimperfectreplacements,couldalsobeintegrated.Acriterionthathasnotbeenconsideredinthisstudy,butthatcouldbeadded,isthecostofthemaintenanceactions.Itcouldbeinte-gratedasaconstraintintheselectivemaintenanceproblem(wedisposeofabudgetfortheachievementofthemaintenanceactions)orT.Lustetal./EuropeanJournalofOperationalResearch197(2009)1166–11771177likeanewcriterion,inmoreofthereliability.ThisproblemhasalreadybeentackledbyLustandTeghem[14]:amulticriteriacombina-torialoptimizationproblemisobtained,becauseitisnecessarytomaximizereliabilityandtominimizethecost(twocontradictorycrite-ria)atthesametime.Thatwouldimplytheinterventionofthedecisionmaker,sinceitwillhavetochoosethesolutioncorrespondingbesttohispreferences.References[1]W.Pierskalla,J.A.Voelker,Asurveyofmaintenancemodels:Thecontrolandsurveillanceofdeterioratingsystems,NavalResearchLogisticsQuarterly23(3)(1976)353–388.[2]Y.Sherif,M.Smith,Optimalmaintenancemodelsforsystemssubjecttofailure:Areview,NavalResearchLogisticsQuarterly28(1981)47–74.[3]D.Cho,M.Parlar,Asurveyofmaintenancemodelsformultiunitsystems,EuropeanJournalofOperationalResearch51(1991)1–23.[4]H.Wang,Asurveyofmaintenancepoliciesofdeterioratingsystems,EuropeanJournalofOperationalResearch139(3)(2002)469–489.[5]W.F.Rice,C.R.Cassady,J.A.Nachlas,Optimalmaintenanceplansunderlimitedmaintenancetime,in:ProceedingsoftheSeventhIndustrialEngineeringResearchConference,1998.[6]C.R.Cassady,W.P.Murdock,E.A.Pohl,Selectivemaintenanceforsupportequipmentinvolvingmultiplemaintenanceactions,EuropeanJournalofOperationalResearch129(1)(2001)252–258.[7]J.H.Zhao,Z.Liu,M.T.Dao,Reliabilityoptimizationusingmultiobjectiveantcolonyapproaches,ReliabilityEngineeringandSystemSafety92(2007)109–120.[8]I.Gertsbakh,ReliabilityTheory:WithApplicationstoPreventiveMaintenance,Springer,2000.[9]J.J.Patton,PreventiveMaintenance,thirded.,ISA–TheInstrumentation,System,andAutomationSociety,2004.[10]K.M.Bretthauer,B.Shetty,Thenonlinearknapsackproblem–Algorithmsandapplications,EuropeanJournalofOperationalResearch138(2001)459–4472.[11]L.Maillart,R.Cassady,C.Rainwater,K.Schneider,Selectivemaintenancedecision-makingoverextendedplanninghorizons,TechnicalReport807,DepartmentofOperations,WeatherheadSchoolofManagement,CaseWesternReserveUniversity,2005.[12]F.Hillier,G.Lieberman,IntroductiontoOperationsResearch,seventhed.,McGraw-Hill,2000.[13]F.Glover,M.Laguna,TabuSearch,KluwerAcademicPublishers,Dordrecht,TheNetherlands,1998.[14]T.Lust,J.Teghem,MulticriteriamaintenanceproblemresolvedbyTabusearch,in:VolumesdesPreprintsdu12thIFACSymposiumonInformationControlProblemsinManufacturing(INCOM’2006),Saint-Etienne,2006,p.6. 因篇幅问题不能全部显示，请点此查看更多更全内容