Queueing Theory In Action, plus, frogs

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:

• The W system requires no customer to make a choice based on incomplete information; the M system basically presents the customer with a roll of the dice. Which queue is fastest? It depends not just on the competence of the cashier, but on whether the transactions pending in a given queue are simple or complex.
• Suppose you are in the M system and two queues -- yours, and the one beside you -- are being serviced at approximately the same rate on average. It is entirely possible and indeed, perhaps common, that even though both queues are in the long run moving at the same rate, that due to sudden starts and stops in both queues you will perceive that you are spending more time "being passed" by the people next to you than "passing" them. It is quite possible for people in both queues to have this perception simultaneously! Everyone feels like they've chosen the wrong queue, even if there is no "wrong queue" on average. In the W system, there is only one queue, so it is automatically the right one.
• The W system is fair; the customer who has waited the longest is always served next. The M system is not fair; customers who happen to be in a "fast" queue can get served before customers in a "slow" queue where they are waiting behind a complex ongoing transaction (or worse, behind a customer who has reached the front of the queue before deciding what to order.)
• The W system has in theory higher possible throughput; the only time that a customer with a fast transaction pending at the front of the queue has to wait a long time is in the unlikely situation that every cashier happens to be busy with a complex transaction. If any cashier is at present serving fast transactions, then they're clearing the front of the queue quickly. In the M system, many fast transactions can get delayed by a single slow one. This drives average throughput way down.
• The W system is far more flexible. New cashiers can be added dynamically when the queue gets too long and removed to perform less pressing tasks when it shortens. In the M system, when a new cashier comes online there can be a disorganized rush to form a new queue; customers are again asked to make a decision about whether to try the new queue or stay in the old one, and this produces new opportunities for perceived unfairness. But worse, when a cashier is removed in the M system, what happens to their queue?

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:

• Jupiter in opposition
• Ganymede
• the Perseid meteor shower
• trout
• frogs
• toads
• tadpoles
• turtles
• turkey vultures
• swallows
• hummingbirds
• mergansers
• loons
• great blue herons
• some kind of predatory bird that was against the sun so I couldn't see it clearly but I suspect it was an osprey
• chipmunks
• bunny rabbits
• silver birch
• snapdragons
• bright green dragonflies
• sheep
• roosters
• fossilized clams
• suspiciously damaged wooden kayak paddles: that is, evidence of beaver-shark activity. But how did they get into my kayak storage over the winter? Are beaver-sharks amphibious?
• my family
• old friends

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.

Comments

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  Meh. I missed the Perseids this year due to cloud cover. Was it spectacular? It was hazy at the peak for me, but we had clear nights on the tail end of it. Not spectacular, but pleasant. Jupiter, being in opposition, was extremely bright and rising just after sunset every night. And even with my poor binoculars, one of the outer moons -- probably Ganymede -- was easily visible. -- Eric

• Anonymous
  August 20, 2009
  Haha @ the wooden paddles.  You positive you locked that storage area?

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  As a former plane mechanic I can tell you that delaying the flight by three hours can never keep the wings from falling off... Thanks for that reassuring thought. :-) -- Eric If there was an actual mechanical problem it would take much longer and they'd probably either get another plane or delay it by at least a day. Maybe they needed to add some oil to the engine? Usually though, as far as I've seen flights get delayed because of personnel issues, or people that just missed the boarding time causing the plane to miss it's take-off window and have to wait for a new free lane. Where were you in your vacation? My family has a summer place on Lake Huron in Ontario. -- Eric

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  Welcome back! Your blog, like a good bottle of wine, just keeps getting better with age. :) Loved how you tied in queueing theory and your vacation. ;) @Benjamin However, Best Buy and Frys (IIRC) manage to pull the W model with large carts. They just sell you something along the entire queue! Win win! So there's less time in the queue potentially, but more product space to sell while in the queue.

• Anonymous
  August 20, 2009
  One of the issues of M v W from a management perspective (and co-queuers perspective) is that in scenario W, the attendant (Q) who is most expedient and efficient sees the most transactions. Meanwhile, the attendant who has gamed the sysem (R) will work as little as possible to still get the job done.  Therefore Q will feel like he/she does more work for the same pay as R. In scenario M, R will be noticed by customers in queue and complains will be directed directly at R. This negative feedback reigns R in a bit. On the other hand, in scenario M, Q wouldn't necessarily be praised because Q would be perceived as doing what Q is supposed to do. Conversely, in scenario W, R's laziness would be attributed to the company (D) not to the attendant at fault. Since the company would like to avoid being blamed generally for the fault of one attendant, M is frequently the preferred scenario for managers, whose task is to maintain the brand regardless of the attendant.

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  The Dr. Demento quote made me laugh while the rest scared the S out of me thinking about an upcoming flight on D airlines.

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  The comment has been removed

• Anonymous
  August 20, 2009
  Sounds like a nice vacation. I can't believe that I completely forgot about the Perseids this year. Shame on me. Anyway, regarding the M vs. W queue models; there is, one more decision model where the M queue might be an advantage to the customer. If time is not an issue, the customer may want to choose the queue with the prettier "server". Of course, this may not be the optimal choice in terms of easy-to-measure goals, but it may be the better choice for that particular customer anyway. However, and I am glad for this, this does not apply to computers.

• Anonymous
  August 20, 2009
  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.

• Anonymous
  August 21, 2009
  The comment has been removed

• Anonymous
  August 21, 2009
  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.

• Anonymous
  August 21, 2009
  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".

• Anonymous
  August 21, 2009
  The comment has been removed

• Anonymous
  August 21, 2009
  The comment has been removed

• Anonymous
  August 21, 2009
  The comment has been removed

• Anonymous
  August 21, 2009
  The comment has been removed

• Anonymous
  August 23, 2009
  The comment has been removed

• Anonymous
  August 24, 2009
  The comment has been removed

• Anonymous
  August 24, 2009
  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.

• Anonymous
  August 24, 2009
  The comment has been removed

• Anonymous
  August 25, 2009
  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.

• Anonymous
  August 27, 2009
  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.

• Anonymous
  August 28, 2009
  The comment has been removed

• Anonymous
  August 28, 2009
  I have been to fast food restaurants that insist on using a particularly bad form of the M system. There are about 12 tills crushed along the serving area, but even at peak times it seems that at most 6 of them are in use. You can tell whether a till is in use only by being at the front of the queue and reading the tiny LED readout. You might think you could tell which are in use by looking at which ones have people behind them, but the staff are constantly moving around fetching orders. So there's pretty much no way for people coming in to tell which tills are in operation. People tend to naturally form into a W system, but there isn't really enough room to form a single queue of much length, and it breaks down when it gets busy. I have been to a local McDonalds where they need to have a member of staff there all the time allocating people into queues because their system is so bad.

• Anonymous
  August 30, 2009
  It's all so obvious once someone points out that to which you've been oblivious for so long.  Great article.

• Anonymous
  September 04, 2009
  "I realize that I am now thinking about work while I'm on vacation, which makes me vexed." "Vexed" is in the class of rarely-used words that deserves to be exercised more frequently.  Bravo.

• Anonymous
  March 05, 2012
  The comment has been removed