- You are here:
- GT Home
Dec 18, 2012 | Atlanta, GA
As industrial engineers, we probably all remember taking various prerequisitemathematics courses like calculusand linear algebra, then moving on tosome of the mathematically orientedcourses within the Stewart School ofIndustrial & Systems Engineering(ISyE) itself. Every once in a while,it’s a good idea to take a step backand think about why all of that mathwas necessary as part of a strong ISyEexperience. This article offers somereminders about the uses and powerof mathematics in our discipline―atleast for those who want to work oncutting-edge applications or emergingresearch areas.
The short story in industrial engineering and operations research is that, for most practical purposes, all of the easy problems and results are gone, having been discovered and thoroughly studied long ago. That doesn’t mean we can’t go out into the world and solve real-life problems with appropriate existing technology; it just means we may have to roll up our mathematical sleeves a bit as we delve into applications that are becoming more and more challenging. For instance, it’s quite easy to “solve” a steady-state single-server queuing system with some simple equations if the customer inter-arrival times and service times are independent and identically distributed exponential random variables. But what if you have an entire network of queues (like, say, a call center or a popular fast-food restaurant) experiencing transient arrival processes that vary throughout the day, or different server schedules and abilities, or equipment breakdowns? These types of problems obviously take a little more effort; a trivial equation isn’t enough.
This article will address some of the mathematics techniques that can be brought to bear on interesting ISyE applications and research problems. You would undoubtedly have been exposed to some of these methods in your travels as a student and in the real world (perhaps, at least, elementary versions), but some may be completely new to you. In any case, the idea is to provide a glimpse of the terrific power of mathematics that’s available for use in problems important to industrial engineers and operations researchers.
Going for a Walk
Let’s begin with a discussion concerning a beautiful application of probability theory and stochastic processes. Of course, the most basic experiment in any probability course is that of flipping a coin. We’ll show how this concept can be turned into something that’s quite sophisticated from a mathematical point of view. Suppose every time I toss tails (T), I earn a dollar, and every time I toss heads (H), I lose a dollar. An interesting question involves that of determining how much money I will have after a certain number of tosses. Where do my total winnings stand after ten tosses? After 100? After one million? As an example, the ten-toss sequence TTTHHTTHTT would have given me a well-deserved net gain of $4.
Such an experiment is called a random walk. Think of me taking a step to the left or a step to the right with equal probability (just like my earnings with the coin flips). In terms of my experiment, I’d like to know where I stand after I’ve been meandering around a while. What’s the probability that I’ll have at least $4 by the tenth toss? Will I earn $4 before I lose $4? But the random walk gives us so much more than a description of the probabilistic behavior of a finite number of coin flips. The magic happens as we increase the number of steps in the random walk, because the process then converges to what is known as Brownian motion.
Here is an example of what an exponential version of Brownian motion looks like (see photo with Associate Professor Shijie Deng). Notice that it bears a striking resemblance to a time series plot of stock prices. In fact, many financial engineers use Brownian motion to model stocks, options, and other financial instruments. Brownian motion is so important and mathematically deep that scientists have won at least two Nobel Prizes explaining it and using it in all sorts of applications. In ISyE, researchers use Brownian motion to:
- analyze what goes on in busy queuing systems (like call centers);
- study the movement of ants;
- model how computer compilers process data lists;
- fit complicated probability distributions;
- develop efficient quality control charts;
- analyze difficult data sets coming out of simulations; and, of course,
- model stock and option process.
Going Nowhere Fast
Speaking of queuing systems as in the last set of examples, how many of us have had to wait in lines a bit more than we would have liked at a store, on the phone, or at an amusement park? The science of queuing (line) theory allows us to analyze the flow of entities through all sorts of systems, where the terms “entities” and “systems” can be quite general. For instance, we might be interested in a problem as simple as that of customer movement through a barber shop (perhaps encountering a tasty barber queue along the way), or more complicated systems such as airport baggage handling services, or a large call center handling millions of customer inquiries.
What are some of the issues involved in queuing theory and how can mathematics help us understand the performance of these types of systems? If you are a customer, you are certainly interested in moving through lines (queues) quickly and being served quickly. If you are the service provider, you may want to keep the lines short in order to save space and avoid customer dissatisfaction. On the other hand, if you are the post office, you’ll likely want to keep the lines nice and long— to show your customers who’s boss. In addition to the issue of line length, you’d want to keep your servers relatively busy―after all, an idle server is the devil’s workshop (and is costing you money). A number of important questions arise from all of these considerations:
- Which one of several lines should I enter at the grocery store’s checkout? Normally, you’d pick the shortest one, but what happens if certain servers are quicker or more talented than others? What happens if you spot particularly slow customers in one of the lines? How about the self-service checkout machine?
- How many servers should I employ? Too many servers cost too much money; too few could cost customers.
- Should we route different types of customers to different service stations in different orders?
- What kind of cross-functionalities should our servers have in order to make the system more efficient?
ISyE researchers study questions such as those described above using a combination of techniques arising from stochastic processes, differential equations, optimization, and computer simulation. The implications of such questions are tremendous and can generate considerations such as:
- How many medical personnel should we schedule in an emergency room?
- Will we have enough voting machines and staff to carry out their proper functions during a national election? And, of course,
- Does The Varsity have enough space to accommodate customers before the next UGA game?
Taking a Tour
Suppose you are a traveling salesman and you need to visit the following cities to show off your goods: Atlanta (A), Buffalo (B), Chicago (C), and Denver (D). Starting from and ending at Atlanta, what’s the best way to do this? This is what ISyE researchers refer to as the Travelling Salesman Problem (TSP).
Here are the possible routes you could take: ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA
Notice that we have six potential routes (or “tours”), corresponding to the six permutations of the cities B, C, D. If we are interested in minimizing the distance travelled, then we really only have to look at the three tours ABCDA, ABDCA, ACBDA since, for example, the distance required for ABCDA is the same as that for ADCBA—assuming we are comfortable walking backward. All we have to do is go on the web and look at the distances for the three routes to get our optimal answer. Pretty simple, right? But what happens if we have n cities on our agenda? Then it is very easy to show that we’ll have to do the look-ups for (n-1)!/2 tours, and this number gets incredibly big very quickly.
Indeed, if we were to try to find the optimal tour by hand for just twenty cities, it would take a huge amount of effort, and it would be exceptionally tedious and time-consuming. Fifty cities by hand would be out of the question. Using mathematical tools from combinatorics, graph theory, and even topology (along with a liberal dose of computer science), ISyE researchers have optimally solved TSPs involving almost 100,000 cities―and they can get nearly optimal solutions for much larger problems! This is not just a pie-in-the-sky mathematical exercise. You can use TSPs to:
- find the optimal route for a delivery truck;
- design the optimal pattern for semiconductor chip etching;
- deliver meals on wheels to homebound infirmed patients; and
- schedule bus pickups for school children.
For more information on TSPs, visit http://www.tsp.gatech.edu/.
Getting from Here to There
Travel is an aspect of all of our lives that ISyE touches in many ways. Think of an airline trip from Atlanta to New York. Typically, you start the process by going online to purchase your ticket at one of the major travel portals (or at the airline itself). The prices you see are dependent on a number of factors, such as time and date of your trip and class of service, and are actually determined by a combination of optimization, regression, and forecasting techniques. For instance, if your airline has determined via its data analytics that the Atlanta-New York route is popular on Labor Day weekend, it will likely try to take advantage of that forecast by keeping most of that route’s prices higher than usual, reducing the number of low-price tickets, reducing the availability of free frequent flier tickets, and perhaps scheduling aircraft with greater capacities.
Your airline almost certainly makes multiple flights from Atlanta to New York every day on a variety of different planes with different capacities. How are the decisions made regarding which planes fly to which cities, at which times, carrying how many people? In particular:
- How does one assign the crew for a specific flight, especially in the presence of tight FAA safety restrictions regarding the amount of time that a crew can serve during a given time period?
- How does one determine flight schedules for a specific aircraft, while adhering to strict maintenance requirements?
- Should the plane fly back and forth between two cities (e.g., Atlanta-New York), or is it more efficient to fly a larger circuit?
- Are hub-and-spoke systems more efficient for your airline than direct point-to-point flights? Should your airline augment its route network with those of smaller commuter airlines?
- Should overbookings be allowed, given proper statistical analysis with respect to no-shows?
- How should staff be assigned and how should the lines be configured at the airport’s security checkpoints?
These are all extremely difficult problems that require the use of optimization, statistical tools, and simulation (among others). ISyE is very lucky to have several researchers specializing in integer programming optimization techniques who are well-known for their work on many of the listed questions. The work―though highly theoretical―has financial consequences that result in millions and millions of dollars in savings.
Follow the Bouncing Ball
As yet another example of mathematics used in our field, let’s talk about something almost every sports fan can relate to: Which college basketball team is going to win the NCAA championship this year? This is a tough problem that involves a number of tricky aspects of probability, statistics, and optimization. The goal is to somehow use our analytical skills from these mathematical areas along with some intelligent data mining to make reasonable predictions (and to win our office pools). In terms of data mining, there’s certainly a lot of information out there. For instance:
- Are the bracket arrangements more helpful to some teams than others?
- Did certain teams already play each other and how did they do?
- Are there any games with obvious home court advantages?
- Are some of the teams currently on a hot streak?
- Do any of the teams have injury issues?
- How have various seeds done in the past?
- Can a team’s margin of victory give us any clues about future performance?
- What about a team’s conference performance?
NCAA tournament prediction is clearly an active area, both from a seat-of-the-pants perspective as well as an analytical perspective. We are very lucky in ISyE to have a number of researchers who have developed an extremely successful prediction technology called the Logistic Regression / Markov Chain (LRMC) method. The interesting name reflects the statistical and probabilistic techniques the tool uses. What is nice about the LRMC ranking system is that it is designed to use only basic scoreboard data: which two teams played, whose court they played on, and what the margin of victory was—though a new so-called Bayesian add-on has been developed recently that allows users to incorporate some gut feeling into the equation.
Obviously, you have to go out and play the games, so you can’t predict things correctly all of the time, but LRMC has done very well compared to just about any other prediction methodology, and ISyE has garnered a great deal of positive play from this terrific application of mathematics. If you would like more information about LRMC, visit http://lrmc.isye.gatech.edu/.
Getting Home Safe and Sound
Another example involving mathematics and modeling in ISyE concerns the important problem of disease propagation. In 2009 and the early part of 2010, the northern hemisphere had to cope with the first waves of a new H1N1 influenza pandemic, also known as swine flu.
Despite high-profile vaccination campaigns in many countries, delays in the administration of vaccination programs were common, and high vaccination coverage levels were not achieved, so the disease was not effectively controlled.
We were lucky this time. This particular strain of swine flu wasn’t too awful in terms of mortality; in fact, it wasn’t much worse than regular seasonal flu. Next time, things might not go our way. So what else could have been done to stem the march of a pandemic disease through the population? ISyE researchers have used a variety of mathematical tools to model the disease as well as certain mitigation strategies. These tools include everything from probability, statistics, differential equations, and optimization, which are then used in conjunction with computer simulations to come up with strategies to mitigate future pandemics. What kinds of strategies are out there?
Here are some possibilities:
- school closure and social distancing
- better vaccination compliance
- more reliable vaccination supply chains
- use and procurement of more effective antiviral medicines
- use of face masks
- working from home
- placement of resources in locations that will allow healthcare officials to respond optimally to a pandemic
Of course, these strategies all cost a great deal of money and some work better than others. ISyE researchers are interested in optimizing health outcomes subject to budget constraints and are actively working in this area.
One advantage of this work is that it can be extended to other healthcare arenas, for instance:
- measles outbreaks
This article has just touched the surface of how the mathematical tools used by ISyE folks can be adopted to solve a variety of theoretical and applied problems. Some of these mathematical technologies are available through courses in ISyE (or from a good math department), but there is no doubt that such cutting-edge methods are required reading for today’s modern practitioners of industrial engineering and operations research.
This article was written by Professor Dave Goldsman and first appeared in the 2012 edition of the ISyE Alumni Magazine.