Clarion University

Operations research, sometimes abbreviated O.R. or often called management science, means a scientific approach to decision making, which seeks to determine what the best design is and how to operate a system. Operations research formally began in the early 1940's in the United States at around the same time it developed in Great Britain. O.R. grew up around military problems (Gue and Thomas 1-2).

During the 1940's there were no mathematical methods of operations research. The only methods that were available were those belonging to individual scientists. One of the first operations research teams was the Blackett's Circus. This team included three physiologists, two mathematical physicists, an astrophysicist, an Army officer, a surveyor, a general physicist, and two mathematicians (Gue and Thomas 1). This group was concerned with the study of military problems.

During World War II the British military leaders asked scientists and engineers to analyze the military's problems. These problems were the deployment of radar and the management of convoy, bombing, antisubmarine, and mining operations (Winston 1). The role of the Blackett's team was to provide scientific assistance in the coordination of British radar equipment at gun sites (Gue and Thomas 1). This is the earliest operations research study. Most of these early studies included teams of civilian scientists working on military problems.

Once the war had ended, interest in operations research outside of military use began to grow. Military was still a center interest in the United States but the second industrial revolution provided an increased interest in O.R. During this new era machines replaced man. "This effect, together with the development of the digital computer and the growing complexity of the management process, provided a fertile environment for the rapid growth of operations research" (Gue and Thomas 2).

This increase led to the development of educational programs. "The Massachusetts Institute of Technology, Case Institute of Technology, and John Hopkins University were early leaders in developing seminars, short courses, and conferences in operations research." These same institutions led the way during the 50's in offering degree programs in operations research (Gue and Thomas 2).

There are three essential parts to an operations research project and a seven step procedure to follow when organizing a problem. The three essential parts are systems orientation, mixed teams, and problem solving. In the systems orientation stage the main concern is with whole problems. This is the realization that every part of a system is connected and has some effect on every other part. Mixed teams is an analysis done by a mixed group of scientists from various fields such as math, economics, psychology and sociology. Problem solving is the approach and methods featured in the project (Gue and Thomas 2-3).

The seven steps are to: 1)formulate the problem, 2) observe the system, 3) formulate a mathematical model , 4) verify the model and use the model for predictions, 5) select a suitable alternative, 6) present the results and conclusions of the study to the organization, and 7) implement and evaluate recommendations. When formulating the problem, the analyst defines the problem of the organization. This includes specifying the objectives and the parts that must be studied before the problem can be solved (Winston 1). Observing the system consists of collecting data to find out what is connected to the problem (Winston 2). When formulating a mathematical model the analyst considers all of the observations and the effects of one thing to another and represents this mathematically. Then he/she creates a situation model which is an equation that lets the computer approximate the behavior of the actual system (Winston 3). Verifying the model requires an analyst to determine if the equation is an accurate display of the problem. This is done by doing the model and figuring out if it fits reality by observing the current situation. If necessary, the equation or model is then updated to fit the situation. Verifying the model is done until the validity of the model under the new situation is correct (Winston 4). Given a model and a set of alternatives the analyst now chooses the alternative that best meets the objectives (Winston 4). The alternative sometimes has restrictions set upon it and may be impossible or costly. "In the next step, the analyst presents the model and recommendation from step 5 to the decision-making individual or group." (Winston 5) Sometimes the organization is given options to choose from. In the last step the model is implemented and the analyst directs the organization in using the new system. The system is monitored to see if it meets the objectives of the organization. If problems do arise, the analyst may start back at creating a new model.

Operations research is concerned with decision problems. There are eight areas of decision problems that can be specified in operations research. They are inventory, allocation, waiting lines, scheduling, sequencing, competition, replacement, and search (Gue and Thomas 8).

Scheduling is important to a wide range of people including government, commerce, machinists, industry, teachers, and students. A schedule is a list of the time certain things are to happen or a timed plan for a project or a list of details (O'Brian 1). Scheduling relates to getting things done. "Scheduling involves the arrangement, coordination, and planning of the utilization of resources to achieve an objective." (O'Brian 2). Time is becoming a scare resource that is most often used in planning.

Scheduling began back in the time of the Egyptians building pyramids and Biblical characters. Biblical examples of scheduling are Noah building the Ark and filling it with the animals and Moses in planning the Exodus from Egypt (O'Brian 2). All wars have involved schedules such as moving troops and strategy planning.

"In the planning of older projects, resources and equipment were the limiting factors. Accordingly, time was a secondary factor, and it was difficult to sharply accelerate programs." (O'Brian 2) Today we have scheduling techniques that try to eliminate these limitations.

The first scientific management techniques were developed in the early 1900's. Frederick W. Taylor is generally recognized as the developer of the scientific management techniques (O'Brian 3). He recognized the short comings of the informal scheduling in his department. Much of his work dealt with industrial production and the use of time and motion to improve the production cycle.

Another developer was Henry L. Gantt who developed the Gantt chart during World War I. This chart was later modified into the bar graph. The Gantt chart is now the standard tool in both product and production scheduling (O'Brian 3). The Gantt chart is used for its simplicity and ease of application.

The development of the computer in the 1950's increased the development of many new scheduling techniques. Computer programs are able to simulate operations research in the form of models (O'Brian 3). These models evolved into what is known today as Critical Path Method (CPM) and Performance Evaluation and Review Technique (PERT). These network based models are the basis for many scheduling techniques.

There are four scheduling techniques and three applications of scheduling. They are time, resource, production, and general scheduling. Functional, Topical and Production are the three important applications (O'Brian 5). Of the techniques, the single most important dimension is time. "The time scheduling techniques are principally based upon network logical plans. The time scheduling techniques CPM, PERT, and Precedence Diagrams all utilize logic nets." (O'Brian 5). Over the years these techniques have become similar and have the same amount of effectiveness. The technique used is up to the person's preference. Other time-based scheduling techniques include close-order, including MTM, time-motion, and short-interval scheduling.

Network models have three important characteristics. First, many real world problems can be modeled by using networks (Buffa and Dyer 264). Problems relating to transportation and distribution are solved using network models. Other types of network models such as CPM and PERT can be used to find the shortest or longest path in a network. The second feature is that the model created of the network has a visual interpretation in addition to the mathematical formulation (Buffa and Dyer 264). The visual representation of a network reduces the problem of communication between the analysis and the organization. This is the most important feature of network models. The last characteristic of the network is that the corresponding mathematical formulation has a special structure that allows extremely large problems to be solved very quickly (Buffa and Dyer 264).

When finding the shortest or longest path in a network, the length of the path is not actually a measure of distance. The path is actually a representation of the money or the time to complete a project (Buffa and Dyer 312). The shortest path is the representation of which path would cost the least and the longest path represents how long it will take for a project to be completely done with the maximal amount of delay.

"One of the most practical and important uses of the concepts of the length of the path through a network is found in network scheduling models. Network scheduling models are used to plan, schedule, control, and evaluate complex projects and tasks." (Buffa and Dyer 318-319). The basic idea is to analyze a project, identify the tasks and relate them in a network.

Networks are common in all of our lives. The highway system is one that we are all familiar with that we have to solve daily. When determining a trip we must decide on a starting point and a destination. The starting point is the initial node and the destination is the terminal node. Next we have to decide all of the alternative routes between these two points. The routes are called arcs which consists of a beginning and ending point and have a direction. The third step we do in planning a trip is which aspect is most important, the shortest path, the scenery, or the comfort. In industry this could be determining if cost, time, or reaching the objective is most important. Next the selection of the route is made and finally the route is reevaluated and corrections are made. (O'Brian 8-9).

Another example of network scheduling in our lives is the academic and industrial areas, networks have been used for many years to describe the flow of processes (O'Brian 9). In the academic area, diagrams or networks have been used to present flows or alternatives. Networks are used to prepare curriculum scheduling.

Computers were important in the development of new techniques of scheduling. "In 1956, the Du Pont Company in Newark, Delaware, decided to utilize its UNIVAC computer in the solution of construction scheduling problems." (O'Brian 12). After the mathematical background was done, the UNIVAC group joined in the effort to create a computer program that would present scheduling information in a format simple enough to be programmed. "James E. Kelley, a mathematician and member of the UNIVAC group, is generally credited with the application of a network to describe the construction logical sequence." (O'Brian 12) Now with this clarity other people realized that networks could have been introduced years ago. CPM and PERT charts were then integrated into a network easier.

A network is made of a series of activities connected by arrows. The events are the nodes and the arrows are the arcs that represent the activity taking place. The arrows have several characteristics: the tail represents the start of the activity and the head represents the completion. The arrows are not drawn to scale nor is it a vector. They may be curved, straight, or bent. The arrow can't be broken by another activity. Time values can be assigned to the activity and the activity can have a zero time value. When assigning time value in a network, the time should be consistent such as in hours and the level of detail in the hour should also be consistent. And finally, activity start and finish points are the events which have no time value. When constructing a network, the area to be diagrammed is divided into parts and the parts are put in order as to what has to be completed before something else can be started. Three questions to ask when developing the network is what activities must come before this one, which ones after it, and which ones must occur with it.

When every arc or arrow has exactly one vertex in common with the previous arc it is called a chain. An example (see figure 1) is going from events (1,2)- (2,3)- (4,3). A path is a chain which the terminal node of each arc is identical to the initial node of the next arc (Winston 311). An example is going from events (1,2)- (2,3)- (3,4). It is unusual for a loop to occur in a network but it is possible. An example is (3,4)- (4,3). Too much detail can hide important facts and become meaningless and so can too little detail.

"The network planning techniques known as the critical path method (CPM) and the Program Evaluation and Review Technique (PERT) were originally developed in the 1950s. PERT was first used to help manage the successful Polaris project, and since that time, some form of network scheduling model has been required for every government defense contract.

The nodes in the network scheduling model represent 'events' in the project. An event generally corresponds to the beginning or end of a specific task, or 'activity,' that must be performed as part of the project. The activities are represented by the arcs in the network.

The rules of logic in the network are relatively simple. Suppose an activity D can be started only after activities A, B, and C have been completed. This situation would be diagrammed as shown in figure 2. Thus, all activities represented by arcs into an event node must be completed before an activity represented by an arc out of an event node can begin." (Buffa and Dyer 320).

The most obvious information of interest is the total length of time required for the project. This time is computed by applying a modified version of the network model. "This algorithm computes the 'earliest' and 'latest' start and finish times for each of the activities. The early start and finish times are simply the earliest that each activity can be started and finished, given the technical precedence relationships in the network. The latest start and finish times are the latest that an activity can be started and finished, without delaying the total time to complete the project. The difference between the early and late start (finish) time is the 'slack' associated with an activity.

This slack is the amount of time that a particular activity could be delayed without delaying the completion of the project. This information can be very useful to managers in scheduling work and the use of equipment. The activities with zero slack can not be delayed without delaying the entire project. These activities are on the longest path through the network, which is called the critical path." (Buffa and Dyer 323)

A specific example of these concepts can be represented in a network model for constructing a house. (Refer to project network for constructing a house handout).

Here we have an initial node (1) and a terminal node (13) for the whole project. There is also starting and ending points for each individual activity. The activity is represented by an arrow or arc. The tail represents the start of the activity and the head represents the completion. This is shown by activity excavate which starts at node 1 and ends at node 2.

Each activity is given a name and an activity time. From node 2 to node 3 we have the activity of the foundation that takes 4 units of time to complete. Some activities are given zero time which is called dummy activities, such as from node 5 to node 8. The reason for this is that node 5 and node 6 both must be completed before node 8 can begin.

The numbers in parenthesis are the earliest starting and finishing times. The first number, starting time, in node 1 is zero because it begins on the very first day. From this point the starting time is found by adding the last starting time plus the activity time. If two activities come into a node such as at node 7 the maximum number is used. This is done till we reach the terminal node (13). At this time we place the same number into the finishing time. The reason 44 is placed there is because we do not want the project to last more tan 44 units of time. Then we work in reverse and subtract the latest finishing time from the activity time. If two activities come into a node such as node 4, the minimum latest time is used. You know you are correct when node 1 is (0,0). The construction of the house meets this requirement.

The red line is the critical path. This is the longest path in the network and the schedule has to be kept to stay on task. We have slack at nodes 6, 8, 10 and 11. As you can see these do not fall on the critical path and can be delayed.

"One important extension is the use of probabilistic time estimates. The time estimate for completing a particular activity may be uncertain, especially in research and development activities where there is no previous experience to use as a guide. Therefore, instead of a single time estimate for an activity , three time estimates are obtained." (Buffa and Dyer 327) The three estimates are optimistic time, pessimistic time and the most likely time. Optimistic time is the shortest possible time to accomplish an activity. Pessimistic time is the longest time that an activity could take under bad conditions. These three estimates are reduced to a single time estimate t_e, the mean of the implied probability distribution for the activity time. Variance can also be estimated s².

t₂=1/6 (a +4m +b) where a is the optimistic time and b is the pessimistic time and m is the most likely time. s²=[1/6(b-a)]². The t₂ estimates are then used in the computation of the critical path for a project exactly as before (Buffa and Dyer 329).

Refer to figure 3

Operations research is used everyday in many companies. The transportation companies depend on network models for its operational plans.

These transportation companies employ a large number of Operations Research specialists. They are used in every area from daily operational planning to long term business development. One of their techniques for operational planning is using network models for transportation systems.

One way in which OR engineers have solved transportation models is through the Shortest Path Method. Package distribution systems are set up in a "hub and spoke" system. Every 250 miles there is one large distribution facility (hub) which receives packages for the smaller facilities (package centers). The hub then splits the packages by zip code to the package centers and the packages are sent out in the delivery vehicles that are seen everyday. The package cars also pick up packages which are loaded into vehicles which the hub distributes to vehicles going all over the world. The transportation example that will be described involves a large hub located in New Stanton, Pennsylvania. Not only does this hub distribute the packages that are picked up and delivered in Western Pennsylvania, but it also is used to consolidate volume in tractor trailers for the Western United States, particularly Washington and Oregon. The facility consolidates volume in hub locations so it can better utilize equipment. If every hub in the eastern United States sent a trailer to Washington then, Washington would receive all trailers that are only 30% full or less. This is why this facility was picked as the consolidation point several years ago. In the time since then, several large shippers to Washington and Oregon have developed in the Philadelphia area. Because of this all the hubs in Eastern Pennsylvania are sending their Washington and Oregon volume across the entire state of Pennsylvania for consolidation when a consolidation in Philadelphia (Willow Grove hub) makes better sense, both logically and financially.

New Stanton is receiving tractor trailers from Lawnside, NJ; Oregon Ave., PA; Lancaster, PA; and Allentown, PA.. These hubs also currently make trailers for Willow Grove hub which is much closer to these locations than New Stanton. New Stanton makes two trailers for Spokane, two for Seattle, and two for Portland. The Willow Grove hub currently makes only one Spokane trailer. Due to the geographic layout, Seattle and Portland packages can be flowed to Spokane and still keep the same days in delivery service. Because of this, Willow Grove is making only a Spokane trailer and flowing all Portland and Seattle volume to Spokane. The problem with this practice is Spokane is then forced to send extra trailers to Seattle and Portland when direct trailers would be a better practice. Since all the trailers going to the west coast are flowed to the west coast on the train, the cost to send a trailer to Seattle as opposed to Spokane is not that great ($25). The cost to send an additional trailer over the ground from Spokane to Seattle is very expensive ($1101).

Because the majority of the volume for Seattle originates in the Philadelphia area, a plan was developed to change the Seattle package flow from Lancaster, Lawnside, Oregon Ave., and Allentown to the Willow Grove hub instead of the New Stanton hub. By changing the flow from these hubs, Willow Grove hub could begin making a Seattle load in addition to the Spokane load it is currently making. The change in the flow would also reduce the number of Spokane loads that New Stanton is making. Between Willow Grove and New Stanton the total number of Washington and Oregon trailers would remain at seven. As stated earlier, the additional cost of additional rail movements is negligible. With this plan though, the ground moves would be greatly reduced. With this change in flow in Pennsylvania, both Lawnside and Lancaster would save a ground movement to New Stanton and add one to Willow Grove. The total savings from this amount to $1148/ day. In addition, this change would save Spokane from processing additional volume and sending a trailer across the state of Washington (round trip 710 miles). The reduction of this ground movement will save $1101 per day. By changing the flow of 1896 packages from New Stanton to Willow Grove, the facility will save $2009/day or $506,243/year.

Refer to sheet 1, "Proposed Spokane Flow Change" and " Existing Feeder Network" and "Proposed Feeder Network"

In conclusion operations research has developed from its mathematical roots in the 1940s to the many applications where it is used today specifically by transportation companies everyday. While the transportation companies don't specifically use any models as CPM or PERT they do use a form of operations research with their transportation modeling for their daily operational movements. Other companies such as the defense department's development of the Polaris missile have used network scheduling techniques in more of a pure form than the transportation industry. But the basis for the analysis is still the same, to optimize the operation and to develop a more cost effective operating system.

Gue, Ronald, and Michael Thomas. Mathematical Methods in Operations Research. New York: Macmillan, 1968.

Buffa, Elwood, and James Dyer. Management Science/ Operations Research. New York: John Wiley and Sons, Inc., 1977.

O'Brian, James. Scheduling Handbook. New York: McGraw-Hill Book Company, 1969.

Winston, Wayne. Operations Research: Applications and Algorithms. Boston: Duxbury, 1987.

Hillier, Frederick, and Gerald Lieberman. Introduction of Operations Scheduling. Fourth Edition. Oakland: Holden-Day Incorporated, 1986.

Chamblin, Michael. Interview. 1995