Fabulous Adventures In Coding
Eric Lippert is a principal developer on the C# compiler team. Learn more about Eric.
Well that was a lovely vacation. It got off to a poor start but then it improved dramatically.
Suppose you've got an "entrance" that is producing some largish number of "customers" on some schedule. You've got a bunch of "servers" who are handling the customer requests. Once a customer request is satisfied, the customer leaves through an "exit". What happens when there are more customers arriving in quick succession than there are available servers to serve them? This is the domain of analytic queueing theory; this theory is germane to a great many human and technical problems, from obtaining a double cheeseburger, onion rings and a large... orange... drink... to routing telephone calls over satellite networks.
(Some of you might be wondering what on earth the first two paragraphs have to do with each other. It'll come together eventually, I promise.)
An interesting example of two different queue servicing algorithms is exemplified by two popular fast food restaurant chains. At restaurant "M", if there are, say, four cashiers then there are four queues. Customers arrive, choose a queue and wait. At restaurant "W", there is one long serpentine queue; when a cashier becomes available, the person at the front of the line goes to that cashier.
The principle downside of the W system is that the single queue looks like it will take much longer than four short queues in the M system, which can be daunting. But by almost every relevant objective metric, by almost every relevant social factor, and in almost every common real-world business scenario the W system is preferable:
It is the importance of this last question that was driven home to me on day one of my vacation. Let's call the airline "D". The D Air Lines baggage check in Seattle-Tacoma International Airport operates on the "M" queueing model. You check yourself in at one of the kiosks, print out your boarding passes, pay your fifteen dollars to check a bag, and then choose one of ten or so queues.
Now, D has at least in theory eliminated one problem with the M model; the last thing the checkin system tells you is which queue to stand in. I do not know how that system decides which queue is best, or whether any customer actually reads the message. It's a subtle thing; I personally was not expecting the system to give me this information, so I could see how someone could miss it entirely and just pick any old queue.
But anyways, we're standing in our assigned queue and its moving along. We don't particularly care how long its taking because our flight has been delayed, allegedly by one hour, due to an "unexpected maintenance issue". So we have plenty of time. (As it turns out, we in reality have over three hours of extra time. Which is fine. Airline mechanics reading this: please take all the time you need to ensure that the wings stay on.) And as we're waiting, I point out something to my wife: the conveyor belt that the luggage is supposed to be going on is not moving. Or rather, it's moving by about one bag width per minute -- jerkily starting up and then halting a second later. Luggage is of course arriving at the front of the queues far, far faster than that, so quite an accumulation of luggage is forming. Most of the "servers" aren't having to walk around, but a few people are walking behind the counter, and it's quite comical to see them trying to manoevre around the increasingly tall stacks of luggage piled beside the now-saturated conveyor.
Leah informs me that her friend C used to be a baggage handler for D Air Lines, but was recently laid off. "Oh, is the recession and slowdown in air travel making for fewer working hours available?" I ask. No, apparently C claims that there was plenty of work for them to do, but the precarious financial state of the airlines has led them to lay off staff and overwork the remaining handlers.
So anyway, we get to the front of the queue and I look up, trying to make eye contact with the D Air Lines representative directly in front of me. She is fixedly looking at the floor and says loudly in the vicinity of the representative serving the queue beside her "I have to leave now." Which she does, continuing to look fixedly at the floor as she walks away. The other representatives, all busy serving other customers, do not react to this news. They may not have heard it. Or, they might have interpreted it as mere information -- as it was stated -- rather than as a request for someone to deal with the now-abandoned queue.
I have plenty of time to wait. So I do. I continue to try to make eye contact with the representatives serving the queues on either side of me, but they are either looking at the person they're serving, or looking with dismay at the growing towers of baggage now thoroughly engulfing the unmoving conveyor belt. I wonder whether it is difficult to miss someone less than two metres away staring at you with an expectant smile for minutes on end. Perhaps D Air Lines trains its staff to be good at that, I muse.
The minutes continue to pass. The queue behind me continues to grow. I reflect upon how this is a failure not just of customer service, but of application of basic results in queueing theory that you'd think an airline would be good at. I realize that I have a blog article in here somewhere, which makes me happy. I realize that I am now thinking about work while I'm on vacation, which makes me vexed. So on balance, it's a wash.
About five minutes into this, the traveller behind me politely taps me on the shoulder and asks "You're going to Michigan too, right? Am I in the right line?"
I turn to half face her, and half face the D Air Lines employee who has been so successfully ignoring me and the couple dozen people behind me. "Ma'am," I say, "look at the larger picture. You are standing in a queue that is being served by no one to put your bags on a conveyor belt that is not moving. Most of the baggage handlers who would be taking your bags off the belt have been fired, and even if there were baggage handlers, the aircraft cannot fly, and probably is not even at this airport. Clearly you and I have not chosen the wrong queue; we have chosen the wrong airline."
Amazingly enough, that aforementioned representative immediately starts servicing our queue.
Though no indication whatsoever that there had been any sort of problem in the first place was forthcoming, to his credit he was polite, seemed reasonably competent at taking my bag, and added my bag to the tower. As we walked away I looked back and saw the fellow now servicing both queues; those queues were now each running at half speed, which I suppose is better than nothing, though I imagine that the people who had chosen either queue were less than thrilled. The airplane did eventually arrive and we did eventually retrieve the bag, so it all worked out in the end.
Now you know why most airlines use the "serpentine" W model rather than the M model. It prevents some of these sorts of problems from happening in the first place.
Things improved considerably after that. A sampling of stuff I saw on my vacation:
The flight home -- where the baggage check was based on the W model -- was uneventful.
And so, back to more fabulous adventures in coding. I hope you enjoyed the pre-canned posted I prepared before my vacation.
Coming up next: one more addendum about iterator blocks.
Actually, Fry's is a good example of what can go bad when you bring the W system to wider scale. the queue ends up being the bottleneck, as the one clerk does not dispatch the incoming customers fast enough to fill all the counter available. At one of the bigger ones I went to, it was often that the queue was full while there were about 5-6 counters available (out of maybe 40-50). Some never filled. And I could see cashiers flailing their arms to the front clerk because they were being ignored...
A good work-stealing implementation may not be fair, but it's usually better at scaling.
In a W scenario, it's trivial to have the machines record how many transactions occur for each attendant. At grocery stores, Best Buy, etc., the attendant enters their information in the register, to record who they are, before they begin a transaction. If at the end of the week, it shows that Q is at the head of the class, recording twice as many transactions per time unit as R (presumably with several employees in between), then it will show up on R's review. R's job therefore becomes much harder: record transactions fast enough not to be at the bottom of the list. Q's job is much simpler: record transactions as fast as possible.
It just occured to me that most fast food restaurants seem to use the W model (the ones with multiple registers anyway), except every McDonald's I've visited in recent memory uses the M model! Odd.
Regarding grocery stores: There's a Meijer in my neighborhood that regularly has huge queues backed up into the aisles. Why? I don't know. What does this have to do with the discussion? Probably nothing.
It occurs to me that if airline "D" is what I think it is, I heard its name applied to an acronym one time that explains quite a few of my service experiences therewith:
"Don't Ever Leave The Airport".
The grocery store phenomenon is not universal! One lovely thing about England is that it's commonplace (though not universal) for grocery stores to use the 'W' method. (Sainsbury, Somerfield, and Tesco go 'W,' while the Co-operative and M&S go 'M.')
The English take their queues seriously.
Just wanted to say welcome back, and thanks for the post! It is rare to encounter such a well-written and approachable discussion of technical theory applied to the real world, that simultaneously makes me struggle to keep from bursting out laughing and disturbing my cube mates :)
I do want to ask though: is that really what you said to the person behind you in line? That's the kind of thing I always imagine myself saying AFTER the fact.
That phenomenon is called "the wit of the staircase" -- that is, you think of the great witty line as you are walking down the front porch stairs away from the party.
Part of the art of storytelling is to emphasize the interesting or important details while trimming away unnecessary cruft that impedes the flow of the narrative. In this particular case though, that is pretty much what I said.
Another time I had a particularly good moment at an airline representative's expense many years ago went like this:
Him: And where are you traveling today?
Me: Toronto, Lester B. Pearson airport.
Him: "Lester B. Pearson"? Geez, do you ever wonder who they name these airports after? Just some guy, I guess.
Me: Pearson was the guy who came up with the idea that the United Nations should have its own peacekeeping forces and was thereby the first Canadian to win the Nobel Peace Prize. He was also largely responsible for getting the maple leaf flag adopted as the national symbol of Canada when he was Prime Minister. But I know what you mean about crazy airport names. "John F. Kennedy" airport in New York I imagine was also named after some guy.
Him: Here's your boarding pass.
Re: queueing at grocery stores
I grew up a dependent of a US Navy service member. Our grocery stores were called the commissary. As I recall (this was before quick check-out lines), the commissary used a long, single queue which wrapped around the store. Once at the head of the queue, an attendent would direct people to the next available cashier with open space for items. Meaning, if there were 20 cashiers, any given cashier may be ringing up items for one customer while a second would be unloading items onto the cart (with a suitable divider, of course). It was possible to have 3 or 4 customers at a check-out if they all had a small number of items.
Some days it took as long to get out of the store as it took to do the shopping. The order items were put in the cart depended as much on how long you anticipated on waiting in addition to the type of items bought on the shopping trip. My sister and I were routinely brought along to act as last-minute gophers as we approached the attendent (you *point* go get the ice cream and popcicles; you *point* go get the frozen meat items).
And welcome back. :)
In response to "One of the issues of M v W from a management perspective (and co-queuers perspective)" by Other Side
Previously having worked in a grocery store as a cashier / drop clerk / dairy box / receiver capacity, I'd like to respectfully comment on a few points you made.
In scenario M, R will be noticed by customers in queue and complains will be directed directly at R.
-- Yes, I'd see this occur regularly
On the other hand, in scenario M, Q wouldn't necessarily be praised
-- No, regular shoppers would get in my line even if it was longer because they knew I was faster and would frequently comment on it.
Gaming the system was also difficult to do because the computers recorded transactions performed by each cashier, and a report was posted each week showing your efficiency. There was a minimum benchmark that the average was compared to and that the individual was compared to. Management could easily see who was failing to meet the minimum standards and would address issues directly.
I almost always had something non-cashier related to be doing, so when I was called up to cashier I would work as efficiently as possible in order to be able to close back down and return to the other task that needed accomplishing.
A side result of being more efficient was that when it came down to volunteers for triple time shifts on holidays, which generally are staffed significantly lower than other days, the more efficient cashiers received priority selectoin.
The big difference between the M and the W model is "who exactly gets served ?" : W model is fair to clients, whereas M model is "fair" to servers : each one has the same workload (and drops his line of pending clients when his time's off) whereas in the W model fast workers get more work.
So to decide which company to fly with, ask this : are decisions governed by the clients best interest or are they the result of negotiations with the employees representatives ?
Oh and, pardon my poor language (I'm french) what the heck is a "Loon" and is there really a species named "Beaver-Shark" ?
Your English is just fine. A loon is a beautiful aquatic bird that is common in Canada. A "loonie" is a silly or crazy person -- probably from lune, that is, someone who has been made crazy by the moon. The loon is the bird on the Canadian one-dollar coin, which is why they're often humourously called "loonies".
A Great Canadian Beaver-Shark is a large, buck-toothed, flat-tailed shark which lives in Lake Huron and eats driftwood, canoe paddles, wooden sailboats and little girls. I enjoy terrifying small children with stories of the beaver-sharks. Regrettably, they are not real. Beaver sharks first appeared in FAIC here. -- Eric
The only grocery store I've seen that uses the W model was a commissary I used to frequent while in the military. They had what looked like a bingo board that lit up with the next available cashier, or a clerk would direct the next person in line to the next cashier. Even CostCo, which seems to have the available room, doesn't implement this model. But, I suppose it's difficult to maneuver a 52" TV and 50 cases of Corona around a serpentine path.
I'm glad you had a nice vacation. Now get back to work.
The problem with W is that it can take some time for the person at the front to see that a desk is free and get to that desk. The problem with M is you can be in the wrong queue.
So why not combine them?
Give each desk it’s own queue that is limited to at most 3 people, then direct the person at the front of the main long queue, to the “mini” queue that has less then 3 people in it. That way the time it takes someone to push the trolley to the mini queue is not lost, as each desk still has someone in front to process.
This can be done by giving each person a ticket number and then displaying over the mini queue the 3 tickets that should go to it.
@Damien: "Loon" is the American English name for what in French would be "plongeon" (the image linked to in Eric's reply would be a "Plongeon huard" in French).
It's a bit confusing for birdwatchers that in British English, Loons are referred to as Divers.
The smaller supermarkets in central London mostly operate the W scheme. Usually there are few enough servers that the customer can easily see where to go when it is their time to step up to a register. In larger supermarkets, the clerks are often on top of the game and will direct you to a counter as they see the current customer there finishing up, thereby negating the time it takes to get to the counter. This tends to work better in the more expensive supermarkets where presumably the staff are paid a bit more and seem to have greater than zero motivation.
I like your idea, Ian, and I have seen something of the sort already in Australia. The supermarkets there will often have M style queues for people with trolleys, and a W style queue for 3 or so servers handling the 12 items or less customers. This keeps the physical size of the W part of the queue down as well.
It seems to me that this kind of combination approach when faced with two different models of processing work in code can often lead to the best efficiency.
As much as I appreciate the W queues at airports, their one disadvantage is that they require moving more often. If you have to wait 10 minutes with 60 people in front of you in a W queue, that means you have to pick up your bags, move them a few feet, and put them down once every 10 seconds on average. If you have to wait 10 minutes with only 10 people in front of you in an M queue, you only have to move your bags once a minute.
This is an awesome blog story!
I agree with Gabe that the M vs W queue has to take into consideration the cost of progressing the queue elements forward. In the case of the toll booth, the cost of moving the entire queue by one car forward is very high and grossly non-linear (increased queue length has great impact on the "stretchiness" of the line).
This reminds me of one fact told by a military colonel back in my university years in Soviet Union (we had mandatory military training classes back then):
When a long military convoy hits the road, the head car travels with a constant speed of about 15 mph, but at the same time the tail car is frequently doing 60-70 mph just to keep up.
This is an example how long W queues may introduce other unforeseen difficulties in managing the queue members.