Here’s a good quiz. I thought of another, operations version:
You’re the gate agent for Delta and the flight is overbooked by two people. You announce in the gate area that anyone who wants to take a later flight should get in line. You’ll give everyone who volunteers a $1000 voucher for future travel on Delta. After you’ve given four vouchers, and you realize there are ten people still in line, do you call you boss to see if you can continue to give out vouchers? Or do you realize you probably should have offered $100 vouchers?
Now, I cannot vouch for the details of this article, which claims that Jerks help traffic move faster and keep jams from happening – hard to believe, eh?
Well imagine that at the busy grocery store, people stood twenty feet away from the end of the checkout counter and waited for the person in front of them to leave before they started putting their food on the checkout counter. The cashier would be standing their with nothing to do during the time between customers, and we can all see that the waiting time for all the other shoppers would go up, right?
Now next time you’re stuck in traffic and notice an empty piece of road in front of you. Many car lengths of bare pavement. Think about the fact that in order to process traffic, each segment of road is like a cashier waiting to “check you out” as you pass by. Cashiers with nothing to do means that there will be a longer wait for you, further back in line.
Now there is a “safe” distance between cars, so I am not advocating tailgating (we all know how badly traffic is affected by rear-end collisions). But excessive amounts of “idle road” means that everyone behind that road space is going to wait longer. So do your part to keep the road filled in.
But try not to seem like too much of a jerk when you’re doing it.
Here’s an article from the NYTimes about a possible return to using nuclear power in Italy. An opponent of the plan said the following:
Emma Bonino, an opposition politician who is vice president of the Italian Senate, said that it made no economic sense to build nuclear plants because they would not be ready for 2o years or longer.
Think about the “production process” to build a nuclear power plant. That would clearly be set up as a “project,” but do you really think the throughput time would be twenty years? What would likely be some of the longest tasks? The bottleneck(s)? Could you arrange tasks in parallel to make the throughput time less than twenty years?
This is something you could research and talk about on your journal page, if you’re interested in this topic.
Now for non-geeks, what does the cartoon in part one mean? When thinking about finding the optimal solution to a problem, one question is how “hard” is the problem. If there are only two solutions, then you could probably spend the time to evaluate both and pick the better one. Most problems have many solutions, and so any algorithm to find the best is going to have to evaluate some number of potential solutions in order to find the best.
This leads to the “order” notation, O(n). What this says is the problem is “order n” and that while we might not know the exact time to evaluate each possible solution, we know we are going to have to check about “n” of them.
Now the traveling salesman problem (TSP) is one where we have to visit some number of locations, one after the other. Suppose I sell golf balls and want to visit five different golf courses today. I start at my house, and I go to one of the golf courses. From there I can choose one of the remaining four. From there, I choose one of the three, and so on, until I return home at the end of the day. How many different ways are there to do this? Turns out that this is the number of permutations of the five (and if you count your home, actually six) locations, and the number of permutations is given by n! = n(n-1)(n-2)…(2)(1). One way to solve the problem is to check every solution, all n! of them.
Suppose there are 10 locations to visit, and that your laptop computer can figure out the length of a trip with a certain visiting sequence in one thousandth of a second. You can come back to your computer in about an hour for the solution. What happens if you add two locations to visit. The awful truth about factorials is they grow like crazy, and now your computer needs five days to find the solution. What to solve 15 locations? It will take your computer 40 years. Ouch.
So geeks try to find sneaky ways to evaluate all the “good” solutions, and implicitly check the others without doing any work. Dynamic programming is one of the sneaky methods for evaluating only some of the possible solutions, but still knowing that the best of the ones you find is better than all of the possible n! solutions. The algorithm in the cartoon is O(n^2 x 2^n). So for 10 locations, we can solve the problem in about one second (instead of an hour). Twelve locations takes four seconds, and 15 takes about a minute. Much better than 40 years!
So geeks win? Not so fast. Try thirty locations — 12 days. Thirty-five locations? A year. Forty locations? 35 years. Don’t even think about 100 locations…
What does O(1) mean? The third panel guy can sell to 100 golf courses by doing just one thing. Okay, you need to have a particularly warped sense of humor to find that funny. But such senses of humor do exist (me, unfortunately).
If you’ve read this far, thanks. But is this problem really important? Do salesmen really do this? Well think about oil delivery trucks or a beer distributor who restocks convenience stores. Lots of locations, lots of choices about who to visit today, and who to visit tomorrow, and the price of gas for your truck keeps going up.
Or think about making printed circuit boards. A robot arm (usually) picks the chips from a storage position (sometimes attached to a tape) and puts them on the board in a particular location. The optimal sequence (the shortest trip to visit the n chip sites on the board) may take a lot less time than a non-optimal one, increasing costs and reducing capacity. Could there be 100 chips on a board? Sure.
We all see barcodes in action at most retail stores, and the increased accuracy that technology allows in collecting sales information opened up all kinds of analysis. A newer technology, radio frequency identification (RFID) takes this one step further by putting a chip on the merchandise that can talk to computers. IBM has a commercial where a truck is lost and it stops at an IBM help desk in the middle of the desert. The drivers ask how the help desk person knew they were lost. She says “the inventory told us.” If the RFID tags know they are supposed to be heading east and they start going north, they could send out a “help us” message. Or a supermarket could tag everything, and when you go to the checkout, a computer could read all of the tags in your cart all at once. Cool, huh?
But one interesting part of technology is that the intended use and the actual uses often diverge. Here’s a company with an interesting application of RFID. Watch where you walk.
The traveling salesman problem is one of a class of “hard” problems, where even if you have insanely fast computers, the solution cannot be verified for thousands of years.
Of course, if you shift the problem setting slightly, the problem can become much easier.
note: this is a geek comic, and I will post what the notation means, and why it is funny (to a certain set of people) in a later post…
The same queueing effects we see in operations happens on the road every day — you can come across a lengthy backup on the Merritt Parkway and find that there was no accident or other “cause” for the delay. This article links to some work in this area. Small amounts of variability have more power to affect things than people realize.
Stanford has a wonderful site that has some videos about how different kinds of products are made.
In operations management, we are careful to look at how economies of scale allow for new products and decreasing costs for existing products — think about how much computing power you can carry around with you that used to take up an entire room (and special air conditioning and a staff of operators). Here’s an interesting article that applies the notion of economies of scale to marriage and divorce.