Saul I. Gass Michael C. Fu Editors Encyclopedia of Operations Research and Management Science Third Edition 1 3 Reference Encyclopedia of Operations Research and Management Science Saul I. Gass (cid:129) Michael C. Fu Editors Encyclopedia of Operations Research and Management Science Third Edition A–I With231Figuresand59Tables Editors SaulI.Gass RobertH.SmithSchoolofBusiness UniversityofMaryland CollegePark,MD,USA MichaelC.Fu RobertH.SmithSchoolofBusinessandInstituteforSystemsResearch UniversityofMaryland CollegePark,MD,USA ISBN978-1-4419-1137-7 ISBN978-1-4419-1153-7(eBook) ISBN978-1-4419-1154-4(printandelectronicbundle) DOI10.1007/978-1-4419-1153-7 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2013949762 1stand2ndeditions:#KluwerAcademicPublishers1996,2001 3rdedition:#SpringerScienceþBusinessMediaNewYork2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe materialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer.PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter. ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheEditorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScienceþBusinessMedia(www.springer.com) Dedication: In Memoriam To the memory of my very dear colleague Saul Irving Gass, an OR pioneer, practitioner, and statesman, and a true scholar and friend. Saul passed away on March 17, 2013, as this edition of the Encyclopedia was going to press. Preface ThegoaloftheEncyclopediaofOperationsResearchandManagementScienceisto providedecisionmakersandproblemsolversinbusiness,industry,government,and academiaacomprehensiveoverviewofthewiderangeofideas,methodologies,and synergistic forces that combine to form the preeminent decision-aiding fields of operations research and management science (OR/MS). The impact of OR/MS on people’squalityoflifeandeconomicwell-beingisastorythatdeservestobetoldin itsfulldetailandglory.TheEncyclopediaofOperationsResearchandManagement Scienceistheprologuetothatstory. The editors, working with the Encyclopedia’s Editorial Advisory Board, surveyed and divided OR/MS into specific topics that collectively encompass the foundations, applications, and emerging elements of this ever-changing field. We also wanted to establish the close associations that OR/MS has maintained with other scientific endeavors, with special emphasis on its symbiotic relationships with computer science, information systems, and mathematics. Based on our broad view of OR/MS, we enlisted a distinguished international group of academics and practitioners to contribute entries on subjects for which they are renowned.Wecommissionedover200majorexpositoryentriesandcomplemented them by numerous descriptions, discussions, definitions, and abbreviations. The connections between topics are highlighted by an entry’s final “See” statement, asappropriate.Eachentryprovidesabackgroundorhistoryofthetopic,describes relevant applications, overviews present and future trends, and lists seminal and current references. To allow for variety in exposition, the authors were instructed to present their material from their research and applied perspectives. In particular, the authors, each of whom is a leading authority on the particular subject,wereallowedtousewhatevermathematicalnotationtheyfeltwasstandard fortheirtopics. TheEncyclopedia’sintendedaudienceistechnicallydiverseandwide;itincludes anyone concerned with the science, techniques, and ideas of how one makes decisions. As this audience encompasses many professions, educational background, and skills, we were attentive to the form, format, and scope of the entries. Thus, the entries are designed to serve as initial sources of information for allsuchreaders,withspecialemphasisontheneedsofstudents. WhatareOperationsResearchandManagementScience? Operationsresearchandmanagementscienceareoftenequatedtooneanother.Ifone definesthembythemethodologiestheyemploy,theequationwouldprobablystand vii viii Preface inspection. If, however, one defines them by their historical developments and the classesofproblemstheyencompass,theequationbecomesfuzzy.ORgrewoutofthe operationalproblemsoftheBritishandU.S.militaryeffortsinWorldWarII.Itwas augmented methodologically and computationally by the postwar developments of linearprogramming,gametheory,dynamicprogramming,discrete-eventsimulation (amongothers),andthedigitalcomputer.Anumberofadditionalideasandproblem types from the pre-war years were incorporated into the field as well, including inventory and queueing theories, Markov modeling, and the basic methods of optimization. Early (1950s) practitioners of OR applied its philosophy and techniques to the solution of industrial and business operational problems with great success. It was soon recognized that whatever OR was as a scientific field, it could be used to study and solve the broader planning and strategic issues of organizational management, financial planning, and public policy. From this observation, MS began and flourished in a similar and somewhat overlapping mannertoOR. MoreformaldefinitionsofORandMSarereadilyavailable.ORcanbedefinedas: (1) the application of the methods of science to complex problems arising in the directionandmanagementoflargesystemsofmen,machine,materials,andmoneyin industry,business,government,anddefense;(2)thescienceofdecidinghowtobest design and operate man-machine systems; (3) a scientific method for providing executive departments with a quantitative basis for decision making. MS can be defined as: (1) the application of scientific methodology or principles to managementdecisions;(2)theuseofquantitativemethodsforsolvingmanagement andorganizationaldecisionproblems.Together,ORandMSmaybethoughtofasthe scienceofoperationalprocesses,decisionmaking,andmanagement.However,toour minds,thedefinitionofOR/MSisreallygivenbythecoverageofthematerialinthis Encyclopedia. SecondEdition The second edition aimed to capture the advances since the 1996 first edition, especially the relationships between OR/MS and information technology, and to update,expand,andcorrecttheoriginalmaterial.WithrespecttoOR/MSadvances, newmaterialrangedfromtheAnalyticNetworkProcesstoDataMiningtoElectronic Commerce to the Theory of Constraints, among the 28 new entries added at that time. First edition entries were updated or rewritten by the original and/or new authors.Basedonsuggestionsfromthereadersofthefirstedition,morematerialon thehistoryofOR/MSwasadded, including emphasis ofitsoriginsbyanarticleon earlyBritishOR. ThirdEdition This third edition of the Encyclopedia of Operations Research and Management Science moves us closer toour goal of providing a comprehensive overview of the theoreticalandappliedsubjectmatterthatformstheever-expandingfieldofOR/MS. Again,manyofthesecondeditionentrieshavebeenupdatedbytheoriginalauthors, Preface ix with a few being totally rewritten by new authors. In addition, the following completely new entries have been added, each of which either describes a new topicorreplacesapreviousshortentry: Agent-BasedSimulation Health Care Strategic Decision AirTrafficManagement Making ApproximateDynamicProgramming Heuristics BusinessIntelligence HitandRunMethods Closed-loopSupplyChains InfluenceDiagrams CombinatorialAuctionTheory KnowledgeManagement CommunityOR LagrangianRelaxation ComplementarityApplications MarkovChainMonteCarlo ComputationalBiology Metaheuristics ConditionalValueatRisk OpenSourceSoftware(andCOIN- ConvexOptimization OR) CriticalSystemsThinking OperationalResearchSociety DataWarehousing PetroleumRefining DecisionAnalysisPractice QuadraticAssignmentProblem DeepUncertainty RareEventSimulation DifferentialGames RegenerativeSimulation DigitalMusic ResponseSurfaceMethodology DisasterManagement RevenueManagement DiseasePrevention,Detection,and SampleAverageApproximation Treatment SensitivityAnalysis FinancialEngineering ServiceScience FlexibleManufacturingSystems SimulatedAnnealing FuzzySets,Systems,and SocietalComplexity Applications StatisticalRankingandSelection GlobalOptimization StochasticApproximation HealthCareManagement StochasticInputModelSelection We want to emphasize that the Encyclopedia of Operations Research and Management Science is the responsibility of the editors. We made the final determination of the scope, topics, and material. Any shortcoming (editorial, inclusion, omission, emphasis, factual) that the reader may perceive rests with us. Hence, we sincerely welcome comments and feedback on all aspects of the Encyclopedia. Acknowledgments WewishtothankallthecontributorstotheEncyclopediaofOperationsResearchand Management Science for their individual efforts and for their cooperation, support, and patience. We would also like to thank the members of the Editorial Advisory Board,pastandpresent,fortheirhelpintheinitialformulationoftheEncyclopedia and their subsequent efforts in reviewing the articles. Last but not least, we are grateful to Springer for their help throughout the process of preparing this third edition, and would specifically like to thank the editorial support provided by JenniferCarlson,ElizabethFerrell,JuliaKoerting,andAnnaleaManalili.