# 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
• 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.

1. Adam V says:

Now I want to come up to SEA-TAC to see which airline operates its baggage check on the M model. (That wouldn’t be the only reason to visit, but I’d make a note to try to figure it out while I’m standing there anyway.)

Has your experience convinced you not to use airline D in the future? Or do you think this was just a one-time issue and you’ll fly with them again? Every time you fly, you’re likely to use SEA-TAC and deal with those same issues on the front end of the trip regardless of the destination, so that would weigh into my decision to fly with D in the future.

Sadly, if I only flew on airlines that never demonstrated massive incompetence, never majorly inconvenienced me or never treated me disrespectfully then the only airlines I’ve tried that I could fly on again are Virgin and British. Sometime I’ll tell you guys about the time I was on a United flight that struck another aircraft. That was big comedy. — Eric

2. Erik says:

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

3. Max says:

Haha @ the wooden paddles.  You positive you locked that storage area?

4. MikeG says:

Are there any advantages to the M model ever? It doesn’t seem so.

Kind of makes you wonder why it is used, e.g. in grocery stores, etc.

Grocery stores are a special case I think. In a grocery store, each queue is typically quite short — it is rare to have more than four people in a line. Grocery stores typically already have a dedicated “ten items or fewer” lane for small, fast checkouts. People in grocery stores have big bulky carts that are unwieldy in a long serpentine queue. Grocery stores are usually laid out so that there is “overflow space” in the form of aisles behind the cashiers; that space is used to sell things in the 99% usage case that there is no overflow. Serpentine queues take up lots of space even when empty; think about how much space in airport terminals is devoted to such queues and how wide they have to be to accomodate baggage carts. Margins are razor-thin in grocery stores so they need to devote as much floor space as possible to selling products. — Eric

5. Actually, grocery stores are about the only case I can see using the M model. Grocery carts are difficult to push around in tight quarters, so a serpentine queue is downright evil. (There’s also the issue of many grocery shoppers checking out a cartload of groceries, so the lanes would get ‘clogged’ fairly quickly. However, this is also a problem with the M model, and can easily be sidestepped by having a hybrid model: a single long queue plus an express lane.)

There are many other interesting aspects peculiar to grocery stores that encourage the M model. For example, grocery stores WANT you to have to wait in the queue because in this model, waiting in the queue is another sales opportunity. That’s why the front place in the queue is stacked with chocolate bars and the second place is stacked with magazines. They know you will be more likely to buy impulse buys if you have to wait. And they know that in order to mitigate the frustration of waiting, they can distract you for two minutes with headlines like How To Get A Man, How To Keep Your Man Away From Other Women Who Probably Read This Magazine Who Want To Take Your Man, and How To Get Rid Of That Good For Nothing Man. A super-efficient queue would actually be worse for grocery stores; slightly inefficient queues allow them to transform even more of their precious square footage into product sales. — Eric

6. configurator says:

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

7. Adam V says:

Another thing about grocery stores is that the line is the very last thing you go to, typically after spending 15-45 minutes filling your cart. Compare to the fast food place, where you have to wait through the line before you can find a table and sit down. A long or slow-moving line at a restaurant will often encourage you to find another place to eat. You won’t go to a different grocery store since you’ve already got the full basket, so the grocery store is less sensitive to long lines. (At least for this trip. They do keep the lines somewhat short/fast so that you don’t go somewhere else next time.)

8. ShawnSt says:

Along the lines of M vs. W in retail stores, a great example of using W in a large scale store would be Fry’s Electronics. (Best Buy does this on a much smaller scale)

Fry’s has a quite long single-turn serpentine queue which is wider to accomodate the shopping carts, and is lined on both sides with all kinds of random junk to sell you while you’re waiting (candy, drinks, movies, games, etc). M style queue would limit the product offerings, since you’d want each person to see the same set of items, whereas the W style queue, everyone sees all the items, and there is a much larger selection. At the end of this queue is a vast array of checkout stations, and a single queue manager employee who directs the front of the queue to the right checkout station as one becomes available. (Sir, please go to register# 27)

There is such an advantage to this W queue style in retail, that I think the only reason it would be a problem are for stores with extended hours where there are greater opportunities for limited customers and perhaps only one available checker to service the queue. In that event, the queue itself is an impediment for someone checking out, as they’d have to navigate the empty queue to check out, rather than going directly to the single open checkout station. This could be mitigated by having a configurable "fast track" passage for off hours to let people quickly check out.

9. Haacked says:

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.

10. Other Side says:

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.

11. Ruaidhrí McDonnell says:

A previous employer of mine did analysis/built solutions for this very problem(those ‘please come to counter N’ installs), and your analysis is identical to the site surveys they did(and a whole lot less).

One variable you might want to consider is the ‘offload speed’, between the queue and the ‘server’. All things being equal, this should be negligible, but in some cases, the offload can be quite high,

supermarkets, as others have pointed out,use the ‘M model’,because amongst other things, people are slow to move their trolleys about,which stalls the entire queue, and so offload time is high, vs a bank where the solution is clearly a ‘W model’.

Another ‘M model’ that works is traffic(toll booths etc).

Incidentally, a few of the supermarkets over here(ireland) have changed to the W model lately. Interesting to see if it works in the long term.

12. KloopDogg says:

The Dr. Demento quote made me laugh while the rest scared the S out of me thinking about an upcoming flight on D airlines.

13. Denis says:

@Ruaidhrí McDonnell,

I would LOVE to see the model W attempted with traffic: first, people from all four lanes trying to form one without bumping into each other and flying into road rage; next, at the end of the queue, putting the steering components of their cars to the test to quickly get to the far-off booth that suddenly becomes available… WOW! π

This could work for some kind of a drive-by, though: imagine people driving along, or around, a set of stalls, or booths, or whatever, until eventually they reach the free one…

…Just imagining aloud, sorry.

14. Aaron Wolski says:

I always enjoyed watching motorists attempt to beat the ‘M’ model as we crawled our way into the city on the heavily congested motorway. The ‘smart’ ones would weave from lane to lane, thinking they had found the fastest moving queue at that particular moment in time, satisfied that they had shaved precious slivers of time off their arduous journey and feeling chuffed about their superior driving technique having saved them a stern word from the boss when they could have just left home 10 minutes earlier. The kicker was that, despite their aggresive, impatient and mostly dangerous queue conquering antics, I’d invariably see those same motorists getting out of their distinctive rides as I pulled into the adjacent car park.

15. 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.

16. bahbar says:

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.

17. Adam V says:

@Other Side:

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.

18. MikeG says:

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.

19. Jim says:

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".

20. Jeff says:

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.

21. David Nelson says:

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.

22. RonO says:

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. π

23. MilesP says:

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.

24. Damien says:

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

25. Casey says:

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.

26. Ian Ringrose says:

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.

27. @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.

28. Niall Connaughton says:

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.

29. Gabe says:

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.

30. Alex O. says:

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.

Alex

31. Weeble says:

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.

32. Brian says:

It’s all so obvious once someone points out that to which you’ve been oblivious for so long.  Great article.

33. Matt Fisher says:

"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.

34. Dan says:

The best model can be "both". This is the immigration model at some airports. You start off in one long serpentine line (for fairness). Then as you approach the booths, break into a line for a specific booth. Each of these lines has just a few people in it.

The reason for this is that it avoids the only problem of the serpentine model – latency. A free agent has to catch the attention of the person at the front of the queue. Some airlines deal with this by having a "router" at the end of the queue who makes sure you see the free agent. But they still have to wait for you to walk from the end of the queue to the free booth.

The hybrid model avoids this problem,because when your queue ends directly in front of a booth, you are less likely to miss when it's free and it's only a couple of strides to get there.