(From Maynard's Industrial Engineering Handbook,5th Edition, pp. 11.27-11.44)
Department of Industrial Engineering, University of Pittsburgh,Pittsburgh,Pennsylvania
This chapter will provide an overview of Operations Research (O.R.)from the perspective of an industrial engineer. The focus of thechapteris on the basic philosophy behind O.R. and the so-called 'O.R.approach'to solving design and operational problems that industrial engineerscommonlyencounter. In its most basic form, O.R. may be viewed as a scientificapproachto solving problems; it abstracts the essential elements of the probleminto a model, which is then analyzed to yield an optimalsolutionfor implementation. The mathematical details and the specifictechniquesused to build and analyze these models can be quite sophisticated andareaddressed elsewhere in this handbook; the emphasis of this chapter isonthe approach. A brief review of the historical origins of O.R.isfollowed by a detailed description of its methodology. The chapterconcludeswith some examples of successful real-world applications of O.R.
A HISTORICAL PERSPECTIVE
WHAT IS OPERATIONS RESEARCH
THE OPERATIONS RESEARCH APPROACH
Validation and Analysis
Implementation and Monitoring
O.R. IN THE REAL WORLD
REFERENCES AND FURTHER READING
An analysis of the data is carried by Taha Operations Research Analysis (TORA) software. Tora for linear programming free download.
Although it is a distinct discipline in its own right, OperationsResearch(O.R.) has also become an integral part of the Industrial Engineering(I.E.)profession. This is hardly a matter of surprise when one considers thatthey both share many of the same objectives, techniques and applicationareas. O.R. as a formal subject is about fifty years old and itsoriginsmay be traced to the latter half of World War II. Most of the O.R.techniquesthat are commonly used today were developed over (approximately) thefirsttwenty years following its inception. During the next thirty or soyearsthe pace of development of fundamentally new O.R. methodologies hasslowedsomewhat. However, there has been a rapid expansion in (1) the breadthof problem areas to which O.R. has been applied, and (2) in themagnitudesof the problems that can be addressed using O.R. methodologies. Today,operations research is a mature, well-developed field with asophisticatedarray of techniques that are used routinely to solve problems in a widerange of application areas.
This chapter will provide an overview of O.R. from the perspectiveofan Industrial Engineer. A brief review of its historical origins isfirstprovided. This is followed by a detailed discussion of the basicphilosophybehind O.R. and the so-called 'O.R. approach.' The chapter concludeswithseveral examples of successful applications to typical problems thatmightbe faced by an Industrial Engineer. Broadly speaking, an O.R. projectcomprisesthree steps: (1) building a model, (2) solving it, and (3) implementingthe results. The emphasis of this chapter is on the first and thirdsteps.The second step typically involves specific methodologies ortechniques,which could be quite sophisticated and require significant mathematicaldevelopment. Several important methods are overviewed elsewhere in thishandbook. The reader who has an interest in learning more about thesetopicsis referred to one of the many excellent texts on O.R. that areavailabletoday and that are listed under 'Further Reading' at the end of thischapter,e.g., Hillier and Lieberman (1995), Taha (1997) or Winston (1994).1.2 A HISTORICAL PERSPECTIVE
While there is no clear date that marks the birth of O.R., it isgenerallyaccepted that the field originated in England during World War II. Theimpetus for its origin was the development of radar defense systems forthe Royal Air Force, and the first recorded use of the term OperationsResearch is attributed to a British Air Ministry official named A. P.Rowewho constituted teams to do 'operational researches' on thecommunicationsystem and the control room at a British radar station. The studies hadto do with improving the operational efficiency of systems (anobjectivewhich is still one of the cornerstones of modern O.R.). This newapproachof picking an 'operational' system and conducting 'research' on how tomake it run more efficiently soon started to expand into other arenasofthe war. Perhaps the most famous of the groups involved in this effortwas the one led by a physicist named P. M. S. Blackett which includedphysiologists,mathematicians, astrophysicists, and even a surveyor. Thismultifunctionalteam focus of an operations research project group is one that hascarriedforward to this day. Blackett’s biggest contribution was in convincingthe authorities of the need for a scientific approach to manage complexoperations, and indeed he is regarded in many circles as the originaloperationsresearch analyst.
O.R. made its way to the United States a few years after itoriginatedin England. Its first presence in the U.S. was through the U.S. Navy’sMine Warfare Operations Research Group; this eventually expanded intotheAntisubmarine Warfare Operations Research Group that was led by PhillipMorse, which later became known simply as the Operations ResearchGroup.Like Blackett in Britain, Morse is widely regarded as the 'father' ofO.R.in the United States, and many of the distinguished scientists andmathematiciansthat he led went on after the end of the war to become the pioneers ofO.R. in the United States.
In the years immediately following the end of World War II, O.R.grewrapidly as many scientists realized that the principles that they hadappliedto solve problems for the military were equally applicable to manyproblemsin the civilian sector. These ranged from short-term problems such asschedulingand inventory control to long-term problems such as strategic planningand resource allocation. George Dantzig, who in 1947 developed thesimplexalgorithm for Linear Programming (LP), provided the single mostimportantimpetus for this growth. To this day, LP remains one of the most widelyused of all O.R. techniques and despite the relatively recentdevelopmentof interior point methods as an alternative approach, the simplexalgorithm(with numerous computational refinements) continues to be widely used.The second major impetus for the growth of O.R. was the rapiddevelopmentof digital computers over the next three decades. The simplex methodwasimplemented on a computer for the first time in 1950, and by 1960 suchimplementations could solve problems with about 1000 constraints.Today,implementations on powerful workstations can routinely solve problemswithhundreds of thousands of variables and constraints. Moreover, the largevolumes of data required for such problems can be stored andmanipulatedvery efficiently.
Once the simplex method had been invented and used, the developmentof other methods followed at a rapid pace. The next twenty yearswitnessedthe development of most of the O.R. techniques that are in use todayincludingnonlinear, integer and dynamic programming, computer simulation,PERT/CPM,queuing theory, inventory models, game theory, and sequencing andschedulingalgorithms. The scientists who developed these methods came from manyfields,most notably mathematics, engineering and economics. It is interestingthat the theoretical bases for many of these techniques had been knownfor years, e.g., the EOQ formula used with many inventory models wasdevelopedin 1915 by Harris, and many of the queuing formulae were developed byErlangin 1917. However, the period from 1950 to 1970 was when these wereformallyunified into what is considered the standard toolkit for an operationsresearch analyst and successfully applied to problems of industrialsignificance.The following section describes the approach taken by operationsresearchin order to solve problems and explores how all of these methodologiesfit into the O.R. framework.
A common misconception held by many is that O.R. is a collection ofmathematical tools. While it is true that it uses a variety ofmathematicaltechniques, operations research has a much broader scope. It is in facta systematic approach to solving problems, which uses one or moreanalyticaltools in the process of analysis. Perhaps the single biggest problemwithO.R. is its name; to a layperson, the term 'operations research' doesnotconjure up any sort of meaningful image! This is an unfortunateconsequenceof the fact that the name that A. P. Rowe is credited with firstassigningto the field was somehow never altered to something that is moreindicativeof the things that O.R. actually does. Sometimes O.R. is referred to asManagement Science (M.S.) in order to better reflect its role as ascientificapproach to solving management problems, but it appears that thisterminologyis more popular with business professionals and people still quibbleaboutthe differences between O.R. and M.S. Compounding this issue is thefactthat there is no clear consensus on a formal definition for O.R. Forinstance,C. W. Churchman who is considered one of the pioneers of O.R. defineditas the application of scientific methods, techniques and tools toproblemsinvolving the operations of a system so as to provide those in controlof the system with optimum solutions to problems. This is indeed arather comprehensive definition, but there are many others who tend togo over to the other extreme and define operations research to be thatwhichoperationsresearchersdo (a definition that seems to be mostoften attributed to E. Naddor)! Regardless of the exact words used, itis probably safe to say that the moniker 'operations research' is hereto stay and it is therefore important to understand that in essence,O.R.may simply be viewed as a systematic and analytical approach todecision-makingand problem-solving. The key here is that O.R. uses a methodologythatis objective and clearly articulated, and is built around thephilosophythat such an approach is superior to one that is based purely onsubjectivityand the opinion of 'experts,' in that it will lead to better and moreconsistentdecisions. However, O.R. does not preclude the use of humanjudgementor non-quantifiable reasoning; rather, the latter are viewed as beingcomplementaryto the analytical approach. One should thus view O.R. not as anabsolutedecision making process, but as an aid to making gooddecisions.O.R. plays an advisory role by presenting a manager or a decision-makerwith a set of sound, scientifically derived alternatives. However, thefinal decision is always left to the human being who has knowledge thatcannot be exactly quantified, and who can temper the results of theanalysisto arrive at a sensible decision.1.4 THE OPERATIONS RESEARCH APPROACH
Given that O.R. represents an integrated framework to help makedecisions,it is important to have a clear understanding of this framework so thatit can be applied to a generic problem. To achieve this, the so-calledO.R.approach is now detailed. This approach comprises the followingsevensequential steps: (1) Orientation, (2) Problem Definition, (3) DataCollection,(4) Model Formulation, (5) Solution, (6) Model Validation and OutputAnalysis,and (7) Implementation and Monitoring. Tying each of these stepstogetheris a mechanism for continuous feedback; Figure 1 shows thisschematically.
Figure 1: The Operations Research Approach
While most of the academic emphasis has been on Steps 4, 5 and 6,thereader should bear in mind the fact that the other steps are equallyimportantfrom a practical perspective. Indeed, insufficient attention to thesestepshas been the reason why O.R. has sometimes been mistakenly looked uponas impractical or ineffective in the real world.
Each of these steps is now discussed in further detail. Toillustratehow the steps might be applied, consider a typical scenario where amanufacturingcompany is planning production for the upcoming month. The companymakesuse of numerous resources (such as labor, production machinery, rawmaterials,capital, data processing, storage space, and material handlingequipment)to make a number of different products which compete for theseresources.The products have differing profit margins and require differentamountsof each resource. Many of the resources are limited in theiravailability.Additionally, there are other complicating factors such as uncertaintyin the demand for the products, random machine breakdowns, and unionagreementsthat restrict how the labor force can be used. Given this complexoperatingenvironment, the overall objective is to plan next month's productionsothat the company can realize the maximum profit possible whilesimultaneouslyending up in a good position for the following month(s).
As an illustration of how one might conduct an operations researchstudyto address this situation, consider a highly simplified instance of aproductionplanning problem where there are two main product lines (widgets andgizmos,say) and three major limiting resources (A, B and C, say) for whicheachof the products compete. Each product requires varying amounts of eachof the resources and the company incurs different costs (labor, rawmaterialsetc.) in making the products and realizes different revenues when theyare sold. The objective of the O.R. project is to allocate theresourcesto the two products in an optimal fashion.
Typically, the team will have a leader and be constituted of membersfrom various functional areas or departments that will be affected byorhave an effect upon the problem at hand. In the orientation phase, theteam typically meets several times to discuss all of the issuesinvolvedand to arrive at a focus on the critical ones. This phase also involvesa study of documents and literature relevant to the problem in order todetermine if others have encountered the same (or similar) problem inthepast, and if so, to determine and evaluate what was done to address theproblem. This is a point that often tends to be ignored, but in ordertoget a timely solution it is critical that one does not reinvent thewheel.In many O.R. studies, one actually adapts a solution procedure that hasalready been tried and tested, as opposed to developing a completelynewone. The aim of the orientation phase is to obtain a clearunderstandingof the problem and its relationship to different operational aspects ofthe system, and to arrive at a consensus on what should be the primaryfocus of the project. In addition, the team should also have anappreciationfor what (if anything) has been done elsewhere to solve the same (orsimilar)problem.
In our hypothetical production planning example, the project teammightcomprise members from engineering (to provide information about theprocessand technology used for production), production planning (to provideinformationon machining times, labor, inventory and other resources), sales andmarketing(to provide input on demand for the products), accounting (to provideinformationon costs and revenues), and information systems (to providecomputerizeddata). Of course, industrial engineers work in all of these areas. Inaddition,the team might also have shopfloor personnel such as a foreman or ashiftsupervisor and would probably be led by a mid-level manager who hasrelationshipswith several of the functional areas listed above. At the end of theorientationphase, the team might decide that its specific objective is to maximizeprofits from its two products over the next month. It may also specifyadditional things that are desirable, such as some minimum inventorylevelsfor the two products at the beginning of the next month, stableworkforcelevels, or some desired level of machine utilization.Problem Definition: This is the second,and in a significant number of cases, the most difficult step of theO.R.process. The objective here is to further refine the deliberations fromthe orientation phase to the point where there is a clear definition ofthe problem in terms of its scope and the results desired. This phaseshouldnot be confused with the previous one since it is much more focused andgoal oriented; however, a clear orientation aids immeasurably inobtainingthis focus. Most practicing industrial engineers can relate to thisdistinctionand the difficulty in moving from general goals such 'increasingproductivity'or 'reducing quality problems' to more specific, well-definedobjectivesthat will aid in meeting these goals.
A clear definition of the problem has three broad components to it.The first is the statement of an unambiguous objective. Along with aspecificationof the objective it is also important to define its scope, i.e., toestablishlimits for the analysis to follow. While a complete system levelsolutionis always desirable, this may often be unrealistic when the system isverylarge or complex and in many cases one must then focus on a portion ofthe system that can be effectively isolated and analyzed. In suchinstancesit is important to keep in mind that the scope of the solutions derivedwill also be bounded. Some examples of appropriate objectives might be(1) 'to maximize profits over the next quarter from the sales of ourproducts,'(2) 'to minimize the average downtime at workcenter X,' (3) 'tominimizetotal production costs at Plant Y,' or (4) 'to minimize the averagenumberof late shipments per month to customers.'
The second component of problem definition is a specification offactorsthat will affect the objective. These must further be classified intoalternativecourses of action that are under the control of the decision maker anduncontrollable factors over which he or she has no control. Forexample,in a production environment, the planned production rates can becontrolledbut the actual market demand may be unpredictable (although it may bepossibleto scientifically forecast these with reasonable accuracy). The ideahereis to form a comprehensive list of all the alternative actions that canbe taken by the decision maker and that will then have an effect on thestated objective. Eventually, the O.R. approach will search for theparticularcourse of action that optimizes the objective.
The third and final component of problem definition is aspecificationof the constraints on the courses of action, i.e., of settingboundariesfor the specific actions that the decision-maker may take. As anexample,in a production environment, the availability of resources may setlimitson what levels of production can be achieved. This is one activitywherethe multifunctional team focus of O.R. is extremely useful sinceconstraintsgenerated by one functional area are often not obvious to people inothers.In general, it is a good idea to start with a long list of all possibleconstraints and then narrow this down to the ones that clearly have aneffect on the courses of action that can be selected. The aim is to becomprehensive yet parsimonious when specifying constraints.
Continuing with our hypothetical illustration, the objective mightbeto maximize profits from the sales of the two products. The alternativecourses of action would be the quantities of each product to producenextmonth, and the alternatives might be constrained by the fact that theamountsof each of the three resources required to meet the planned productionmust not exceed the expected availability of these resources. Anassumptionthat might be made here is that all of the units produced can be sold.Note that at this point the entire problem is stated in words;lateron the O.R. approach will translate this into an analytical model.
One of the major driving forces behind the growth of O.R. has beentherapid growth in computer technology and the concurrent growth ininformationsystems and automated data storage and retrieval. This has been a greatboon, in that O.R. analysts now have ready access to data that waspreviouslyvery hard to obtain. Simultaneously, this has also made thingsdifficultbecause many companies find themselves in the situation of beingdata-richbut information-poor. In other words, even though the data is allpresent'somewhere' and in 'some form,' extracting useful information fromthesesources is often very difficult. This is one of the reasons whyinformationsystems specialists are invaluable to teams involved in any nontrivialO.R. project. Data collection can have an important effect on thepreviousstep of problem definition as well as on the following step of modelformulation.
Edius 6 free download for android. To relate data collection to our hypothetical production example,basedupon variable costs of production and the selling price of each of theproducts, it might be determined that the profit from selling one gizmois $10 and one widget is $9. It might be determined based on time andworkmeasurements that each gizmo and each widget respectively requires 7/10unit and 1 unit of resource 1, 1 unit and 2/3 unit of resource 2 and1/10unit and 1/4 unit of resource 3. Finally, based upon prior commitmentsand historical data on resource availability, it might be determinedthatin the next month there will be 630 units of resource 1, 708 units ofresource2 and 135 units of resource 3 available for use in producing the twoproducts.
It should be emphasized that this is only a highly simplifiedillustrativeexample and the numbers here as well as the suggested data collectionmethodsare also vastly simplified. In practice, these types of numbers canoftenbe very difficult to obtain exactly, and the final values are typicallybased on extensive analyses of the system and represent compromisesthatare agreeable to everyone on the project team. As an example, amarketingmanager might cite historical production data or data from similarenvironmentsand tend to estimate resource availability in very optimistic terms. Onthe other hand, a production planner might cite scrap rates or machinedowntimes and come up with a much more conservative estimate of thesame.The final estimate would probably represent a compromise between thetwothat is acceptable to most team members.Model Formulation: This is the fourthphaseof the O.R. process. It is also a phase that deserves a lot ofattentionsince modeling is a defining characteristic of all operations researchprojects. The term 'model' is misunderstood by many, and is thereforeexplainedin some detail here. A model may be defined formally as a selectiveabstractionof reality. This definition implies that modeling is the process ofcapturingselected characteristics of a system or a process and then combiningtheseinto an abstract representation of the original. The main idea here isthat it is usually far easier to analyze a simplified model than it isto analyze the original system, and as long as the model is areasonablyaccurate representation, conclusions drawn from such an analysis may bevalidly extrapolated back to the original system.
There is no single 'correct' way to build a model and as oftennoted,model-building is more an art than a science. The key point to be keptin mind is that most often there is a natural trade-off between theaccuracyof a model and its tractability. At the one extreme, it may be possibleto build a very comprehensive, detailed and exact model of the systemathand; this has the obviously desirable feature of being a highlyrealisticrepresentation of the original system. While the very process ofconstructingsuch a detailed model can often aid immeasurably in betterunderstandingthe system, the model may well be useless from an analyticalperspectivesince its construction may be extremely time-consuming and itscomplexityprecludes any meaningful analysis. At the other extreme, one couldbuilda less comprehensive model with a lot of simplifying assumptions sothatit can be analyzed easily. However, the danger here is that the modelmaybe so lacking in accuracy that extrapolating results from the analysisback to the original system could cause serious errors. Clearly, onemustdraw a line somewhere in the middle where the model is a sufficientlyaccuraterepresentation of the original system, yet remains tractable. Knowingwhereto draw such a line is precisely what determines a good modeler, andthisis something that can only come with experience. In the formaldefinitionof a model that was given above, the key word is 'selective.' Having aclear problem definition allows one to better determine the crucialaspectsof a system that must be selected for representation by the model, andthe ultimate intent is to arrive at a model that captures all the keyelementsof the system while remaining simple enough to analyze.
Models may be broadly classified into four categories:
Physical Models: These are actual, scaled down versions oftheoriginal. Examples include a globe, a scale-model car or a model of aflowline made with elements from a toy construction set. In general, suchmodelsare not very common in operations research, mainly because gettingaccuraterepresentations of complex systems through physical models is oftenimpossible.
Analogic Models: These are models that are a step down fromthefirst category in that they are physical models as well, but use aphysicalanalogto describe the system, as opposed to an exact scaled-down version.Perhapsthe most famous example of an analogic model was the ANTIACmodel(the acronym stood for anti-automatic-computation) whichdemonstrated that one could conduct a valid operations researchanalysiswithout even resorting to the use of a computer. In this problem theobjectivewas to find the best way to distribute supplies at a military depot tovarious demand points. Such a problem can be solved efficiently byusingtechniques from network flow analysis. However the actual procedurethatwas used took a different approach. An anthill on a raised platform waschosen as an analog for the depot and little mounds of sugar on theirownplatforms were chosen to represent each demand point. The network ofroadsconnecting the various nodes was constructed using bits of string withthe length of each being proportional to the actual distance and thewidthto the capacity along that link. An army of ants was then released attheanthill and the paths that they chose to get to the mounds of sugarwerethen observed. After the model attained a steady state, it was foundthatthe ants by virtue of their own tendencies had found the most efficientpaths to their destinations! One could even conduct some postoptimalityanalysis. For instance, various transportation capacities along eachlinkcould be analyzed by proportionately varying the width of the link, anda scenario where certain roads were unusable could be analyzed bysimplyremoving the corresponding links to see what the ants would then do.Thisillustrates an analogic model. More importantly, it also illustratesthatwhile O.R. is typically identified with mathematical analysis, the useof an innovative model and problem-solving procedure such as the onejustdescribed is an entirely legitimate way to conduct an O.R. study.
Computer Simulation Models: With the growth in computationalpower these models have become extremely popular over the last ten tofifteenyears. A simulation model is one where the system is abstracted into acomputer program. While the specific computer language used is not adefiningcharacteristic, a number of languages and software systems have beendevelopedsolely for the purpose of building computer simulation models; a surveyof the most popular systems may be found in OR/MS Today (October 1997,pp. 38-46). Typically, such software has syntax as well as built-inconstructsthat allow for easy model development. Very often they also haveprovisionsfor graphics and animation that can help one visualize the system beingsimulated. Simulation models are analyzed by running the software oversome length of time that represents a suitable period when the originalsystem is operating under steady state. The inputs to such models arethedecision variables that are under the control of the decision-maker.Theseare treated as parameters and the simulation is run for variouscombinationsof values for these parameters. At the end of a run statistics aregatheredon various measures of performance and these are then analyzed usingstandardtechniques. The decision-maker then selects the combination of valuesforthe decision variables that yields the most desirable performance.
Simulation models are extremely powerful and have one highlydesirablefeature: they can be used to model very complex systems without theneedto make too many simplifying assumptions and without the need tosacrificedetail. On the other hand, one has to be very careful with simulationmodelsbecause it is also easy to misuse simulation. First, before using themodelit must be properly validated. While validation is necessary with anymodel,it is especially important with simulation. Second, the analyst must befamiliar with how to use a simulation model correctly, including thingssuch as replication, run length, warmup etc; a detailed explanation ofthese concepts is beyond the scope of this chapter but the interestedreadershould refer to a good text on simulation. Third, the analyst must befamiliarwith various statistical techniques in order to analyze simulationoutputin a meaningful fashion. Fourth, constructing a complex simulationmodelon a computer can often be a challenging and relatively time consumingtask, although simulation software has developed to the point wherethisis becoming easier by the day. The reason these issues are emphasizedhereis that a modern simulation model can be very flashy and attractive,butits real value lies in its ability to yield insights into very complexproblems. However, in order to obtain such insights a considerablelevelof technical skill is required.
A final point to keep in mind with simulation is that it does notprovideone with an indication of the optimal strategy. In some sense it is atrialand error process since one experiments with various strategies thatseemto make sense and looks at the objective results that the simulationmodelprovides in order to evaluate the merits of each strategy. If thenumberof decision variables is very large, then one must necessarily limitoneselfto some subset of these to analyze, and it is possible that the finalstrategyselected may not be the optimal one. However, from a practitioner’sperspective,the objective often is to find a good strategy and notnecessarilythebest one, and simulation models are very useful in providing adecision-makerwith good solutions.
Mathematical Models: This is the final category of models,andthe one that traditionally has been most commonly identified with O.R.In this type of model one captures the characteristics of a system orprocessthrough a set of mathematical relationships. Mathematical models can bedeterministic or probabilistic. In the former type, all parameters usedto describe the model are assumed to be known (or estimated with a highdegree of certainty). With probabilistic models, the exact values forsomeof the parameters may be unknown but it is assumed that they arecapableof being characterized in some systematic fashion (e.g., through theuseof a probability distribution). As an illustration, the Critical PathMethod(CPM) and the Program Evaluation and Review Technique (PERT) are twoverysimilar O.R. techniques used in the area of project planning. However,CPM is based on a deterministic mathematical model that assumes thattheduration of each project activity is a known constant, while PERT isbasedon a probabilistic model that assumes that each activity duration israndombut follows some specific probability distribution (typically, the Betadistribution). Very broadly speaking, deterministic models tend to besomewhateasier to analyze than probabilistic ones; however, this is notuniversallytrue.
Most mathematical models tend to be characterized by three mainelements:decision variables, constraints and objective function(s). Decisionvariables are used to model specific actions that are under thecontrolof the decision-maker. An analysis of the model will seek specificvaluesfor these variables that are desirable from one or more perspectives.Veryoften – especially in large models – it is also common to defineadditional'convenience' variables for the purpose of simplifying the model or formaking it clearer. Strictly speaking, such variables are not under thecontrol of the decision-maker, but they are also referred to asdecisionvariables. Constraints are used to set limits on the range ofvaluesthat each decision variable can take on, and each constraint istypicallya translation of some specific restriction (e.g., the availability ofsomeresource) or requirement (e.g., the need to meet contracted demand).Clearly,constraints dictate the values that can be feasibly assigned to thedecisionvariables, i.e., the specific decisions on the system or process thatcanbe taken. The third and final component of a mathematical model is theobjectivefunction. This is a mathematical statement of some measure ofperformance(such as cost, profit, time, revenue, utilization, etc.) and isexpressedas a function of the decision variables for the model. It is usuallydesiredeither to maximize or to minimize the value of the objective function,depending on what it represents. Very often, one may simultaneouslyhavemore than one objective function to optimize (e.g., maximize profits andminimize changes in workforce levels, say). In such cases there are twooptions. First, one could focus on a single objective and relegate theothers to a secondary status by moving them to the set of constraintsandspecifying some minimum or maximum desirable value for them. This tendsto be the simpler option and the one most commonly adopted. The otheroptionis to use a technique designed specifically for multiple objectives(suchas goal programming).
In using a mathematical model the idea is to first capture all thecrucialaspects of the system using the three elements just described, and tothenoptimize the objective function by choosing (from among all values forthe decision variables that do not violate any of the constraintsspecified)the specific values that also yield the most desirable (maximum orminimum)value for the objective function. This process is often calledmathematicalprogramming. Although many mathematical models tend to follow thisform,it is certainly not a requirement; for example, a model may beconstructedto simply define relationships between several variables and thedecision-makermay use these to study how one or more variables are affected bychangesin the values of others. Decision trees, Markov chains and many queuingmodels could fall into this category.
Before concluding this section on model formulation, we return toourhypothetical example and translate the statements made in the problemdefinitionstage into a mathematical model by using the information collected inthedata collection phase. To do this we define two decision variables Gand W to represent respectively the number of gizmos andwidgetsto be made and sold next month. Adobe fuse cc download mac. Then the objective is to maximize totalprofits given by 10G+9W. There is a constraint corresponding toeach of the three limited resources, which should ensure that theproductionof G gizmos and W widgets does not use up more of thecorrespondingresource than is available for use. Thus for resource 1, this would betranslated into the following mathematical statement 0.7G+1.0W≤630, where the left-hand-side of the inequality represents theresourceusage and the right-hand-side the resource availability. Additionally,we must also ensure that each G and W valueconsidered isa nonnegative integer, since any other value is meaningless in terms ofour definition of G and W. The completely mathematicalmodelis:
- 0.7G+1.0W ≤ 630
- 1.0G+(2/3)W ≤ 708
- 0.1G+0.25W ≤ 135
- G, W ≥ 0 andintegers.
At the lowest level one might be able to use simple graphicaltechniquesor even trial and error. However, despite the fact that the developmentof spreadsheets has made this much easier to do, it is usually aninfeasibleapproach for most nontrivial problems. Most O.R. techniques areanalyticalin nature, and fall into one of four broad categories. First, there aresimulation techniques, which obviously are used to analyze simulationmodels.A significant part of these are the actual computer programs that runthemodel and the methods used to do so correctly. However, the moreinterestingand challenging part involves the techniques used to analyze the largevolumes of output from the programs; typically, these encompass anumberof statistical techniques. The interested reader should refer to a goodbook on simulation to see how these two parts fit together. The secondcategory comprises techniques of mathematical analysis used to addressa model that does not necessarily have a clear objective function orconstraintsbut is nevertheless a mathematical representation of the system inquestion.Examples include common statistical techniques such as regressionanalysis,statistical inference and analysis of variance, as well as others suchas queuing, Markov chains and decision analysis. The third categoryconsistsof optimum-seeking techniques, which are typically used to solve themathematicalprograms described in the previous section in order to find the optimum(i.e., best) values for the decision variables. Specific techniquesincludelinear, nonlinear, dynamic, integer, goal and stochastic programming,aswell as various network-based methods. A detailed exposition of theseisbeyond the scope of this chapter, but there are a number of excellenttextsin mathematical programming that describe many of these methods and theinterested reader should refer to one of these. The final category oftechniquesis often referred to as heuristics. The distinguishing featureofa heuristic technique is that it is one that does not guarantee that thebestsolution will be found, but at the same time is not as complexas an optimum-seeking technique. Although heuristics could be simple,common-sense,rule-of-thumb type techniques, they are typically methods that exploitspecific problem features to obtain good results. A relatively recentdevelopmentin this area are so-called meta-heuristics (such as genetic algorithms,tabu search, evolutionary programming and simulated annealing) whicharegeneral purpose methods that can be applied to a number of differentproblems.These methods in particular are increasing in popularity because oftheirrelative simplicity and the fact that increases in computing power havegreatly increased their effectiveness.
In applying a specific technique something that is important to keepin mind from a practitioner's perspective is that it is oftensufficientto obtain a good solution even if it is not guaranteed to bethebestsolution. If neither resource-availability nor time were an issue, onewould of course look for the optimum solution. However, this is rarelythe case in practice, and timeliness is of the essence in manyinstances.In this context, it is often more important to quickly obtain asolutionthat is satisfactory as opposed to expending a lot of effort todeterminethe optimum one, especially when the marginal gain from doing so issmall.The economist Herbert Simon uses the term 'satisficing' to describethisconcept - one searches for the optimum but stops along the way when anacceptably good solution has been found.
At this point, some words about computational aspects are in order.When applied to a nontrivial, real-world problem almost all of thetechniquesdiscussed in this section require the use of a computer. Indeed, thesinglebiggest impetus for the increased use of O.R. methods has been therapidincrease in computational power. Although there are still large scaleproblemswhose solution requires the use of mainframe computers or powerfulworkstations,many big problems today are capable of being solved on desktopmicrocomputersystems. There are many computer packages (and their number is growingby the day) that have become popular because of their ease of use andthatare typically available in various versions or sizes and interfaceseamlesslywith other software systems; depending on their specific needsend-userscan select an appropriate configuration. Many of the software vendorsalsooffer training and consulting services to help users with getting themostout of the systems. Some specific techniques for which commercialsoftwareimplementations are available today include optimization/ mathematicalprogramming (including linear, nonlinear, integer, dynamic and goalprogramming),network flows, simulation, statistical analysis, queuing, forecasting,neural networks, decision analysis, and PERT/CPM. Also available todayare commercial software systems that incorporate various O.R.techniquesto address specific application areas including transportation andlogistics,production planning, inventory control, scheduling, location analysis,forecasting, and supply chain management. Some examples of popular O.R.software systems include CPLEX, LINDO, OSL, MPL, SAS, and SIMAN, tonamejust a few. While it would clearly be impossible to describe herein thefeatures of all available software, magazine such as OR/MS Todayand IE Solutions regularly publish separate surveys of variouscategoriesof software systems and packages. These publications also providepointersto different types of software available; as an example, the December1997issue of OR/MS Today (pages 61-75) provides a complete resourcedirectory for software and consultants. Updates to such directories areprovided periodically. The main point here is that the ability to solvecomplex models/problems is far less of an issue today than it was adecadeor two ago, and there are plenty of readily available resources toaddressthis issue.
We conclude this section by examining the solution to the modelconstructedearlier for our hypothetical production problem. Using linearprogrammingto solve this model yields the optimal solution of G=540 and W=252,i.e.,theproductionplan that maximizes profits for the given data callsfor the production of 540 gizmos and 252 widgets. The reader may easilyverify that this results in a profit of $7668 and fully uses up all ofthe first two resources while leaving 18 units of the last resourceunused.Note that this solution is certainly not obvious by just looking at themathematical model - in fact, if one were 'greedy' and tried to make asmany gizmos as possible (since they yield higher profits per unit thanthe widgets), this would yield G=708 and W=0 (at whichpointall of the second resource is used up). However, the resulting profitof$7080 is about 8% less than the one obtained via the optimal plan. Thereason of course, is that this plan does not make the most effectiveuseof the available resources and fails to take into account theinteractionbetween profits and resource utilization. While the actual differenceissmall for this hypothetical example, the benefits of using a good O.R.technique can result in very significant improvements for largereal-worldproblems.Validation and Analysis: Once a solutionhas been obtained two things need to be done before one even considersdeveloping a final policy or course of action for implementation. Thefirstis to verify that the solution itself makes sense. Oftentimes, this isnot the case and the most common reason is that the model used was notaccurate or did not capture some major issue. The process of ensuringthatthe model is an accurate representation of the system is calledvalidationand this is something that (whenever possible) should be done beforeactualsolution. However, it is sometimes necessary to solve the model todiscoverinaccuracies in it. A typical error that might be discovered at thisstageis that some important constraint was ignored in the model formulation- this will lead to a solution that is clearly recognized as beinginfeasibleand the analyst must then go back and modify the model and re-solve it.This cycle continues until one is sure that the results are sensibleandcome from a valid system representation.
The second part of this step in the O.R. process is referred to aspostoptimalityanalysis, or in layperson's terms, a 'what-if' analysis. Recall thatthemodel that forms the basis for the solution obtained is (a) a selectiveabstraction of the original system, and (b) constructed using data thatin many cases is not 100% accurate. Since the validity of the solutionobtained is bounded by the model's accuracy, a natural question that isof interest to an analyst is: 'How robust is the solution with respectto deviations in the assumptions inherent in the model and in thevaluesof the parameters used to construct it?' To illustrate this with ourhypotheticalproduction problem, examples of some questions that an analyst mightwishto ask are, (a) 'Will the optimum production plan change if the profitsassociated with widgets were overestimated by 5%, and if so how?' or(b)'If some additional amount of Resource 2 could be purchased at apremium,would it be worth buying and if so, how much?' or (c) 'If machineunreliabilitywere to reduce the availability of Resource 3 by 8%, what effect wouldthis have on the optimal policy?' Such questions are especially ofinterestto managers and decision-makers who live in an uncertain world, and oneof the most important aspects of a good O.R. project is the ability toprovide not just a recommended course of action, but also details onitsrange of applicability and its sensitivity to model parameters.
Before ending this section it is worth emphasizing that similar to atraditional Industrial Engineering project, the end result of an O.R.projectis not a definitive solution to a problem. Rather, it is an objectiveanswerto the questions posed by the problem and one that puts thedecision-makerin the correct 'ball-park.' As such it is critical to temper theanalyticalsolution obtained with common sense and subjective reasoning beforefinalizinga plan for implementation. From a practitioner's standpoint a sound,sensibleand workable plan is far more desirable than incremental improvementsinthe quality of the solution obtained. This is the emphasis of thispenultimatephase of the O.R. process.
In this section some examples of successful real-world applicationsof operations research are provided. These should give the reader anappreciationfor the diverse kinds of problems that O.R. can address, as well as forthe magnitude of the savings that are possible. Without any doubt, thebest source for case studies and details of successful applications isthe journal Interfaces, which is a publication of the Institutefor Operations Research and the Management Sciences (INFORMS). Thisjournalis oriented toward the practitioner and much of the exposition is inlaypersons'terms; at some point, every practicing industrial engineer should referto this journal to appreciate the contributions that O.R. can make. Allof the applications that follow have been extracted from recent issuesof Interfaces.
Before describing these applications, a few words are in order aboutthe standing of operations research in the real world. An unfortunaterealityis that O.R. has received more than its fair share of negativepublicity.It has sometimes been looked upon as an esoteric science with littlerelevanceto the real-world, and some critics have even referred to it as acollectionof techniques in search of a problem to solve! Clearly, this criticismis untrue and there is plenty of documented evidence that when appliedproperly and with a problem-driven focus, O.R. can result in benefitsthatcan be quite spectacular; the examples that follow in this sectionclearlyattest to this fact.
On the other hand, there is also evidence to suggest that(unfortunately)the criticisms leveled against O.R. are not completely unfounded. Thisis because O.R. is often not applied as it should be - people haveoftentaken the myopic view that O.R. is a specific method as opposedto a complete and systematic process. In particular, there hasbeenan inordinate amount of emphasis on the modeling and solution steps,possiblybecause these clearly offer the most intellectual challenge. However,itis critical to maintain a problem-driven focus - the ultimate aim of anO.R. study is to implement a solution to the problem beinganalyzed.Building complex models that are ultimately intractable, or developinghighly efficient solution procedures to models that have littlerelevanceto the real world may be fine as intellectual exercises, but runcontraryto the practical nature of operations research! Unfortunately, thisfacthas sometimes been forgotten. Another valid criticism is the fact thatmany analysts are notoriously poor at communicating the results of anO.R.project in terms that can be understood and appreciated bypractitionerswho may not necessarily have a great deal of mathematicalsophisticationor formal training in O.R. The bottom line is that an O.R. project canbe successful only if sufficient attention is paid to each of the sevensteps of the process and the results are communicated to the end-usersin an understandable form.
Some examples of successful O.R. projects are now presented.
In the orientation phase it was determined that the MRP type systemsused by a number of its competitors would not be a satisfactory answerand a decision was made to develop a planning system that would meetHarris'unique needs - the final result was IMPReSS, an automated productionplanningand delivery quotation system for the entire production network. Thesystemis an impressive combination of heuristics as well asoptimization-basedtechniques. It works by breaking up the overall problem into smaller,moremanageable problems by using a heuristic decomposition approach.Mathematicalmodels within the problem are solved using linear programming alongwithconcepts from material requirements planning. The entire systeminterfaceswith sophisticated databases allowing for forecasting, quotation andorderentry, materials and dynamic information on capacities. Harrisestimatesthat this system has increased on-time deliveries from 75% to 95% withno increase in inventories, helped it move from $75 million in lossesto$40 million in profits annually, and allowed it to plan its capitalinvestmentsmore efficiently.Gasoline Blending at Texaco: Foranotherapplication to production planning, but this time in a continuous asopposedto discrete production environment, we look at a system in use atTexaco. One of the major applications of O.R. is in the area of gasolineblendingat petroleum refineries, and virtually all major oil companies usesophisticatedoptimization models in this area. At Texaco the system is calledStarBlendand runs on networked microcomputers. As some background, thedistillationof crude petroleum produces a number of different products at differentdistillation temperatures. Each of these may be further refined throughcracking (where complex hydrocarbons are broken into simpler ones) andrecombination. These various output streams are then blended togethertoform end-products such as different grades of gasoline (leaded,unleaded,super-unleaded etc.), jet fuel, diesel and heating oil. The planningproblemis very complex, since different grades of crude yield differentconcentrationsof output streams and incur different costs, and since differentend-productsfetch different revenues and use different amounts of refineryresources.Considering just one product - gasoline - there are various propertiesthat constrain the blends produced. These include the octane number,leadand sulfur content, volatilities and Reid vapor pressure, to name afew.In addition, regulatory constraints impose certain restrictions aswell.
As an initial response to this complex problem, in the early to mid1980's Texaco developed a system called OMEGA. At the heart of this wasa nonlinear optimization model which supported an interactive decisionsupport system for optimally blending gasoline; this system alone wasestimatedto have saved Texaco about $30 million annually. StarBlend is anextensionof OMEGA to a multi-period planning environment where optimal decisionscould be made over a longer planning horizon as opposed to a singleperiod.In addition to blend quality constraints, the optimization model alsoincorporatesinventory and material balance constraints for each period in theplanninghorizon. The optimizer uses an algebraic modeling language called GAMSand a nonlinear solver called MINOS, along with a relational databasesystemfor managing data. The whole system resides within a user-friendlyinterfaceand in addition to immediate blend planning it can also be used toanalyzevarious 'what-if' scenarios for the future and for long-term planning.
At Caterpillar, a preliminary analysis showed that the FMS was beingunderutilized and the objective of the project was to define a goodproductionschedule that would improve utilization and free up more time toproduceadditional parts. In the orientation phase it was determined that theenvironmentwas much too complex to represent it accurately through a mathematicalmodel, and therefore simulation was selected as an alternative modelingapproach. It was also determined that minimizing the makespan (which isthe time required to produce all daily requirements) would be the bestobjective since this would also maximize as well as balance machineutilization.A detailed simulation model was then constructed using a specializedlanguagecalled SLAM. In addition to the process plans required to specify theactualmachining of the various part types, this model also accounted for anumberof factors such as material handling, tool handling and fixturing.Severalalternatives were then simulated to observe how the system wouldperformand it was determined that a fairly simple set of heuristic schedulingrules could yield near optimal schedules for which the machineutilizationswere almost 85%. However, what was more interesting was that this studyalso showed that the stability of the schedule was strongly dependentonthe efficiency with which the cutting tools used by the machines couldbe managed. In fact, as tool quality starts to deteriorate the systemstartsto get more and more unstable and the schedule starts to fall behindduedates. In order to avoid this problem, the company had to suspendproductionover the weekends and replace worn-out tools or occasionally useovertimeto get back on schedule. The key point to note from this application isthat a simulation model could be used to analyze a highly complexsystemfor a number of what-if scenarios and to gain a better understanding ofthe dynamics of the system.Fleet Assignment at Delta Airlines: Oneofthemostchallenging as well as rewarding application areas of O.R.has been the airline industry. We briefly describe here one suchapplicationat Delta Airlines . The problem solved is often referred to as thefleetassignment problem. Delta flies over 2500 domestic flight legs each dayand uses about 450 aircraft from 10 different fleets, and the objectivewas to assign aircraft to flight legs in such a way that revenues fromseats are maximized. The tradeoff is quite simple - if a plane is toosmallthen the airline loses potential revenue from passengers who cannot beaccommodated on board, and if it is too large then the unoccupied seatsrepresent lost revenue (in addition to the fact that larger aircraftarealso more expensive to operate). Thus the objective is to ensure thatanaircraft of the 'correct' size be available when required and whererequired.Unfortunately, ensuring that this can happen is tremendouslycomplicatedsince there are a number of logistical issues that constrain theavailabilityof aircraft at different times and locations.
The problem is modeled by a very large mixed-integer linear program- a typical formulation could result in about 60,000 variables and40,000constraints. The planning horizon for each problem is one day since theassumption is made that the same schedule is repeated each day(exceptionssuch as weekend schedules are handled separately). The primaryobjectiveof the problem is to minimize the sum of operating costs (includingsuchthings as crew cost, fuel cost and landing fees) and costs from lostpassengerrevenues. The bulk of the constraints are structural in nature andresultfrom modeling the conservation of flow of aircraft from the differentfleetsto different locations around the system at different scheduled arrivaland departure times. In addition there are constraints governing theassignmentof specific fleets to specific legs in the flight schedule. There arealsoconstraints relating to the availability of aircraft in the differentfleets,regulations governing crew assignments, scheduled maintenancerequirements,and airport restrictions. As the reader can imagine, the task ofgatheringand maintaining the information required to mathematically specify allof these is in itself a tremendous task. While building such a model isdifficult but not impossible, the ability to solve it to optimality wasimpossible until the very recent past. However, computational O.R. hasdeveloped to the point that it is now feasible to solve such complexmodels;the system at Delta is called Coldstart and uses highly sophisticatedimplementationsof linear and integer programming solvers. The financial benefits fromthis project were tremendous; for example, according to Delta thesavingsduring the period from June 1 to August 31, 1993 were estimated atabout$220,000 per day over the old schedule.
Tora Software For Operation Research Machine Learning
The first step was the development of a computerized system tocapturedata on performance. The system captured the beginning and ending timeof all components of a teller transaction including host response time,network response time, teller controlled time, customer controlled timeand branch hardware time. The data gathered could then be analyzed toidentifyareas for improvement. Queuing theory was used to determine staffingneedsfor a prespecified level of service. This analysis yielded a requiredincreasein staffing that was infeasible from a cost standpoint, and thereforeanestimate was made of the reductions in processing times that would berequiredto meet the service objective with the maximum staffing levels thatwerefeasible. Using the performance capture system, KeyCorp was then abletoidentify strategies for reducing various components of the servicetimes.Some of these involved upgrades in technology while others focused onproceduralenhancements, and the result was a 27% reduction in transactionprocessingtime. Once the operating environment was stabilized, KeyCorp introducedthe two major components of SEMS to help branch managers improveproductivity.The first, a Teller Productivity system, provided the manager withsummarystatistics and reports to help with staffing, scheduling andidentifyingtellers who required further training. The second, a Customer Wait Timesystem, provided information on customer waiting times by branch, bytimeof day and by half-hour intervals at each branch. This system usedconceptsfrom statistics and queuing theory to develop algorithms for generatingthe required information. Using SEMS, a branch manager could thusautonomouslydecide on strategies for further improving service. The system wasgraduallyrolled out to all of KeyCorp's branches and the results were veryimpressive.For example, on average, customer processing times were reduced by 53%and customer wait times dropped significantly with only four percent ofcustomers waiting more than five minutes. The resulting savings over afive year period were estimated at $98 million.Summary
This chapter provides an overview of operations research, itsorigins,its approach to solving problems, and some examples of successfulapplications.From the standpoint of an industrial engineer, O.R. is a tool that cando a great deal to improve productivity. It should be emphasized thatO.R.is neither esoteric nor impractical, and the interested I.E. is urgedtostudy this topic further for its techniques as well as itsapplications;the potential rewards can be enormous.
- Leachman, R. C., R. F. Benson, C. Liu and D. J. Raar,'IMPReSS:An AutomatedProduction-Planning and Delivery-Quotation System at Harris Corporation- Semiconductor Sector,' Interfaces, 26:1, pp. 6-37, 1996.
- Rigby, B., L. S. Lasdon and A. D. Waren, 'The Evolution ofTexaco'sBlending Systems: From OMEGA to StarBlend,' Interfaces, 25:5,pp.64-83, 1995.
- Flanders, S. W. and W. J. Davis, 'Scheduling a FlexibleManufacturingSystem with Tooling Constraints: An Actual Case Study,' Interfaces,25:2,pp.42-54,1995.
- Subramanian, R., R. P. Scheff, Jr., J. D. Quillinan, D. S.WiperandR. E. Marsten, 'Coldstart: Fleet Assignment at Delta Air Lines,', Interfaces,24:1,pp.104-120,1994.
- Kotha, S. K., M. P. Barnum and D. A. Bowen, 'KeyCorp ServiceExcellenceManagement System,' Interfaces, 26:1, pp. 54-74, 1996.
- Hillier, F. S. and G. J. Lieberman, IntroductiontoOperationsResearch, McGraw-Hill Publishing Company, New York, NY, 1995.
- Taha, H. A., Operations Research,PrenticeHall, UpperSaddle River, NJ, 1997.
- Winston, W. L., Operations Research,Duxbury Press,Belmont, CA, 1994.