XX人寿保险公司KPI体系设计(修改）

InvitedReviewAsurveyforthequadraticassignmentproblemqElianeMariaLoiolaa,NairMariaMaiadeAbreua,PauloOswaldoBoaventura-Nettoa,PeterHahnb,*,TaniaQueridoc,1aFederalUniversityofRiodeJaneiro,BrazilbDepartmentofElectricalandSystemsEngineering,UniversityofPennsylvania,2127TryonStreet,Philadelphia,PA19146-1228,UnitedStatescFederalCenterforTechnologicalEducation,BrazilReceived13September2004;accepted2September2005Availableonline27December2005AbstractThequadraticassignmentproblem(QAP),oneofthemostdifficultproblemsintheNP-hardclass,modelsmanyreal-lifeproblemsinseveralareassuchasfacilitieslocation,parallelanddistributedcomputing,andcombinatorialdataanalysis.Combinatorialoptimizationproblems,suchasthetravelingsalesmanproblem,maximalcliqueandgraphpar-titioningcanbeformulatedasaQAP.Inthispaper,wepresentsomeofthemostimportantQAPformulationsandclassifythemaccordingtotheirmathematicalsources.Wealsopresentadiscussiononthetheoreticalresourcesusedtodefinelowerboundsforexactandheuristicalgorithms.Wethengiveadetaileddiscussionoftheprogressmadeinbothexactandheuristicsolutionmethods,includingthoseformulatedaccordingtometaheuristicstrategies.Finally,weanalyzethecontributionsbroughtaboutbythestudyofdifferentapproaches.2005ElsevierB.V.Allrightsreserved.Keywords:Assignment;Integerprogramming;Combinatorialoptimization;Facilitiesplanninganddesign;Metaheuristics;Branchandbound1.IntroductionLetusconsidertheproblemofassigningfacilitiestolocationsinsuchawaythateachfacilityisdesignatedtoexactlyonelocationandvice-versa.Thedistancesbetweenlocations,thedemandflows0377-2217/$-seefrontmatter2005ElsevierB.V.Allrightsreserved.doi:10.1016/j.ejor.2005.09.032qApreliminaryversionofthissurvey,with278references,isLoiolaetal.(2004).*Correspondingauthor.E-mailaddresses:[e-mail](E.M.Loiola),[e-mail](N.M.M.deAbreu),[e-mail](P.O.Boaventura-Netto),[e-mail](P.Hahn),[e-mail](T.Querido).1Presentaddress:UniversityofFlorida,Gainesville,supportedbyCNPq,Brazil.EuropeanJournalofOperationalResearch176(2007)657–690fiesthequadraticassignmentproblem(QAP)astheproblemoffindingamin-imumcostallocationoffacilitiesintolocations,takingthecostsasthesumofallpossibledistance-flowproducts.ThemainmotivationforthissurveyisthecontinuousinterestinQAP,shownbyanumberofresearch-ersworldwide,forthetheory,applicationsandsolutiontechniquesforthisproblem.Amongthemanyref-erenceslistedattheendofthispaper,wefoundover100thatwerepublishedsince1999.Thelastsurveys,booksandreviewarticlesintheliteratureareBurkard(1991),Malucelli(1993),Pardalosetal.(1994),Bur-kardandC¸ela(1996),C¸ela(1998)andBurkardetal.(1998a).ThearticleofAnstreicher(2003)reviewsonlytherecentadvancesonalgorithms.AnarticlebyDrezneretal.(inpress)surveysthestate-of-the-artinbothheuristicandexactmethods.KoopmansandBeckmann(1957)firstproposedtheQAPasamathematicalmodelrelatedtoeconomicactivities.Sincethen,ithasappearedinseveralpracticalapplications:Steinberg(1961)usedtheQAPtominimizethenumberofconnectionsbetweencomponentsinabackboardwiring;Heffley(1972,1980)appliedittoeconomicproblems;FrancisandWhite(1974)developedadecisionframeworkforassigninganewfacility(policeposts,supermarkets,schools)inordertoserveagivensetofclients;GeoffrionandGraves(1976)focusedonschedulingproblems;Pollatscheketal.(1976)invokedtheQAPtodefinethebestdesignfortypewriterkeyboardsandcontrolpanels;KrarupandPruzan(1978)appliedittoarcheology;Hubert(1987)instatisticalanalysis;Forsbergetal.(1994)useditintheanalysisofreactionchemistryandBruscoandStahl(2000)innumericalanalysis.Nevertheless,thefacilitieslayoutproblemisthemostpopularapplicationfortheQAP:DickeyandHopkins(1972)appliedtheQAPtotheassignmentofbuild-ingsinaUniversitycampus,Elshafei(1977)inahospitalplanningandBos(1993)inaproblemrelatedtoforestparks.Benjaafar(2002)introducedaformulationofthefacilitylayoutdesignprobleminordertominimizework-in-process(WIP).Inhiswork,heshowsthatlayoutsobtainedusingaWIP-basedformu-lationcanbeverydifferentfromthoseobtainedusingtheconventionalQAP-formulation.Forexample,aQAP-optimallayoutcanbeWIP-infeasible.RabakandSichman(2003),Mirandaetal.(2005)andDumanandIlhan(inpress)studiedtheplacementofelectroniccomponents.Theindexassignmentproblem(Ben-DavidandMalah,2005)hastodowitherrorcontrolincommuni-cationsandcanbeshowntobeaspecialcaseoftheQAP.WessandZeitlhofer(2004)studiedtheproblemofmemorylayoutoptimizationinsignalprocessors.OtherapplicationscanbefoundinScriabinandVer-gin(1975),HubertandSchulz(1976),Heffley(1977),Los(1978),Khareetal.(1988a,b),Krackhardt(1988),BlandandDawson(1991),Balakrishnanetal.(1992),LacksonenandEnscore(1993),Medova(1994),Phil-lipsandRosen(1994),GouveiaandVoß(1995),BozerandSuk-Chul(1996),TalbotandCawley(1996),White(1996),MasonandRo¨nnqvist(1997),OstrowskiandRuoppila(1997),Balletal.(1998),HaghaniandChen(1998),Kochharetal.(1998),Martin(1998),Sarkeretal.(1998),SpiliopoulosandSofianopou-lou(1998),Tansela