Hacker News new | past | comments | ask | show | jobs | submit login
Queueing theory: The science of waiting in line (johndcook.com)
299 points by chmaynard on Jan 23, 2019 | hide | past | favorite | 134 comments

Understanding the basics of queueing theory means that you will be eternally frustrated in most US grocery store checkout lines. And you may be kicked out for screaming "Basically zero-cost queue synchronization and heavily variable server time means a global queue is better!"

It's true, but there are two things to factor in:

1) People tend to sort themselves by picking the shortest line.

2) Grocery stores try to staff only just enough registers so that no register ever has a gap.

If you combine those two things, the efficiency closes in on what a global queue would. My main gripe is the "unlucky" factor where the shopper gets stuck behind a very slow person, which the global queue would fix.

The third, dark-patterny part of this is how grocers benefit from people and their children being stuck next to impulse merchandise while they wait.

My local cinema concession stand moved from a single queue to one queue per register. The variance increased noticeably every time I have visited since and all the staff I have spoken to hated the change and said they were regularly getting complaints about it. When I asked why they changed I was told one of the managers did it because it made the lines shorter and they concluded that meant the wait must also be shorter.

You're not factoring the perception of the multiple shorter lines vs a long line. It's can be the difference between someone glancing who might/might not want popcorn and jumping in line (which ends up taking longer, but they're already committed) vs looking at a single LONG line, and deciding not to bother.

A Whole Foods near me used to have a system with a global queue, where you would sort into multiple lines (e.g. A, B, C, D) and there would be a screen saying which line's turn it was to send someone (A first, then B, then C, then D, rinse and repeat). It was pretty quick and nobody seemed to mind it much

You can have your cake and eat it too, it turns out.

The problem I noticed with the system like this is that cashier is idling for a bit while the next customer walks from the head of single line to the specific register. Depending on the layout this can be a significant distance. There’s no such idling in multiple lines.

That is why some places started to use hybrid system. One single line until very end where someone marshals you at the end of many very short lines.

I should be clear; there are actually multiple lines and multiple registers. It's just that no line corresponds to a specific register.

Imagine four lines arranged next to each other, at the head of eight registers arranged similarly to a self-checkout area. There will always be four people at the head of the lines. The first person in the first line gets to go, then the first person in the second line, then the first person in the third line, then the first person in the fourth line, and then it cycles back.

Because in practice it is extremely rare for four out of eight registers to simultaneously open up, the next person is always at the front of their line already, which avoids this particular travel distance problem.

I also regularly go to a Whole Foods with this system, it initially felt like a good compromise between "one slow cashier shouldn't hang up a lot of people" and "people react negatively to long lines, even if they're fast-moving".

The way this particular one works is with color codes -- there are four color-coded lanes, and when a cashier becomes available, they are announced by the system, which cycles through the colors.

It has some failure modes.

In the "dilute limit", if a customer approaches the lines and there's nobody else there, there's no indication of which color was last called or which is next, so they have to guess. If they guess wrong and someone else shows up and guesses right before a cashier becomes available, they might lose out. This effect goes away once the system acquires "memory", by having people in the queue who have seen the last cashier announcement.

At moderate congestion, it can be hard to assess which lane is shortest, because people don't space themselves evenly, and sometimes go up in groups. People have a pretty strong sense of fair play, and I've seen people grumbling when the system breaks the expected FIFO dynamic.

But, generally speaking, it works better than I thought it would when they first set it up.

I should be clear and say that the Whole Foods I was at used this color scheme; I just used letters for illustrative purposes :)

The Whole Foods that I live near now uses a single line heading to multiple express registers, as well as traditional checkouts. This seems to be the worst of both worlds; not only can I not tell which traditional checkout will finish first, I also can't really tell how long the single express queue is actually moving! Are registers opening up at a regular pace or are they opening in waves? It's honestly the worst.

I had an awful experience with this system the last time I went to a Whole Foods. The problem was that there was insufficient signage explaining the system, and the computer announcer was quite vague about who should go up. When a register was free, the computer spoke “next”, not “A” or “D”; if there was a screen with the letter, it wasn’t easily visible. In fact, I didn’t even notice the tiny signs labeling each line while I was standing in line.

As a result, when I was at the front of line “A” and the computer called “next” after the other lines had gone, I went forward, but another customer did too. The other customer ended up cussing me out for going ahead of him – it turned out he was in a “D” line that, from my “A” line, looked like part of the “C” line. Being yelled at for not understanding the rules of a poorly explained system made for a unpleasant experience.

Fry’s does the same thing with the screen (used to have a human for it), with a single global queue.

Same thing; never had a concern with it. But whole foods and fry’s are bigger and I end up spending a good deal of time there just shopping uaually, so queue length isn’t as concerning as when I’m in a smaller grocery, just grabbing a gallon of milk

Maybe purchasing a text book on Queueing theory and giving it to one of the staff would help, topics that dense tend to change minds quickly when they are disseminated at high velocity toward management.

You may read that as you please.

Flips to a page with a formula using sigma notation

"This isn't rocket science bro. Obviously more lines = faster."

A German chain for electric goods (Saturn) switched to a global queue recently (the first person in the queue gets called to the next available register). I find it a much better customer experience.

With multiple lines, there's also the excellent visual cue to managers - if the average line length appears too long, you know you need additional cashiers. And my local grocery store is excellent about bringing in additional cashiers if any of the lines are two deep or more.

With a global line, the length of the line isn't a good visual indicator of needing more cashiers. I suppose you could just periodically count the line length, and count the cashiers, and divide, but it's not a quick eye check anymore.

In the airports line to the passport control is usually global and formed into a switchback pattern by belt barriers. Sometimes out of boredom I measure the time it takes me to go one full section and multiply by the number of sections in front of me. Turns out to be a very good approximation of a total waiting time.

A global line solves another problem: with multiple lines, when additional cashiers are added, it tends to be the people at the back of the current lines move their way into the front positions of the newly opened lines.

It happens this way because people who are further in the line are generally “in the channel” and can’t slip out as easily... at least in grocery stores.

I was at a severely overloaded grocery store pre-storm this past weekend, which had implemented two global queues (one for 20 items or less, one for everyone else) in order to attempt to increase throughput and block the store less.

The manager was actually going around asking people at the front of the line the time they got in line, in order to be able to measure time in queue. Didn't really matter, as they had every lane open already, but seemed like a way for the manager to know if more lanes were needed.

Or they just mark the line with "one cashier reasonable wait time" and "two cashier reasonable wait time" marks, and then add a cashier whenever the line is past the mark.

Global line length is no different than average line length of multiple lines.

On a global average that is probably true. On an individual/personal level it is not. I take a strategic approach, there might be twice as many people in one line but it will be faster. No one in that line is breaking out the check book. They won't be arguing about a 25 cent coupon that expired. On the plus side I've noticed less places accepting checks. Personally I think they should be banned for basic consumer shopping entirely. Unless it is 4 digits, use a card or cash.

As for self checkout lines there should be a huge sign that asks "are you prepared for this technology?, Really? Are you sure?"

It is when the number of lines (cashiers) changes.

True. You'd need to see transactions per customer-in-store or some other leveling metric...not just customer ready to pay.

Trader Joe's uses a single line (in every one I've ever been to) and it is wonderful. Even a line wrapping the entire store will only take 10-15 minutes because they staff appropriately and you're almost always moving.

You also are always next to some kind of food item and the impulse buys are staged in an even longer display than in a regular grocery store. Instead of four feet wide and five feet tall, it may be 20-30 feet wide and 3-4 feet tall.

I’ve never seen a single line TJs. And that’s across four States.

The ones I'm referring to are in Manhattan and Philadelphia.

If you're ever in downtown San Francisco, half the TJ store is the line when it's a little crowded!

It's absurd. Works pretty well though!

For the record, it's the only TJ's in SF that does this. And I agree, it works well given how much traffic it gets.

Same design in the downtown Boston branch. Line snakes through entire store with lots of opportunity to pick up things along the way.

It might be a SF thing or downtown thing, where there isn’t room for multiple lines.

None of the other SF stores are single line.

Same. VA / WI

> Trader Joe's uses a single line (in every one I've ever been to)

Multiple lines in western Washington, FWIW.

My Tj's has a single line at the front of the store (likely optimized for those taking public transport and purchasing fewer groceries). But in the back, where the parking lot is, it's a queue per register.

Multiple lines at Trader Joes in Westwood LA.

Phoenix area TJ's use multiple lines

Multiple lines in Oregon.

>My main gripe is the "unlucky" factor where the shopper gets stuck behind a very slow person, which the global queue would fix.

Yeah, but that’s one important metric you should judge a queuing system by: standard deviation of wait time. It means entrants are less able to allocate their own time, since they have to anticipate higher variance.

In fact that's not how supermarkets evaluate queuing. They evaluate strategies based on exposing you to the most items while waiting - or you can check yourself out for the "discount" of not being exposed to impulse items.

Target did a trial of a global queue in a store near me, it lasted about a year.

I had a family member that worked at Target, and I asked about why they have 40ish registers, but normally only <10 of them are open. It's all about the holiday shopping. Those ~8 weeks see so much traffic it is worth the "wasted" square footage in the store the other 10 months of the year.

I actually don't like global queueing for the simple reason that I have to keep moving. In a local queue, I can stop and ignore the world for a minute.

My favorite solution is that adopted by my local Trader Joe's. They use local queues, but somehow seem to magically always have just enough checkouts open that at most one person is waiting in each queue. Further, the queues are not separated from each other by barriers, so when a cashier empties their queue (a common occurrence), they can steal customers from neighboring queues.

In fact this system works so well that I don't think I've ever had to finish waiting for the person ahead of me in my chosen queue. Almost invariably, either there is a free register, or another cashier steals me before I reach the head of my queue.

I think this system is enabled partly by the fact that Trader Joe's are almost always small enough that workers can be summoned to cashier duty from anywhere in the store in a matter of seconds. Traditional supermarkets are too large to be able to react so quickly to workload variance, leading them to rely on deep queues to keep cashiers busy.

(Not all Trader Joe's are blessed with this system. There is one in Boston, the smallest TJ's in the nation, which, owing to its size, must resort to a global queue which, at peak hours, snakes its way through all aisles of the store such that the only means of shopping is to first get in the checkout line, and then to add things to your basket as you slowly make your way to the checkout. I suppose in some sardonic sense this is the most efficient of all systems, if you are purchasing items from all sections of the store anyway.)

If I remember correctly, in the mathematical model a global queue only helps with variance, but not the expected waiting time or throughput.

In the real world you won't have the same service time for both cases since you need to add in walking from the global queue to the individual registers.

You will end up with increased confusion from customers who always have to be on the lookout for next open spot at slightly higher waiting time and a more confusing store layout, all for just lower variance. Is it worth it?

The Target by my house implemented global queuing at the registers and honestly, it’s the nicest store to shop at.

Similarly, I’m not sure the global queue adds more than a step or two to routing, since you have to walk to the register either way, and it replaces a complex mental task, picking the optimal queue then monitoring if you should switch, with a simple one, waiting in a line while looking for a wave. In my experience, a global queue is less taxing than having to queue in lines would be.

Yes, agreed, this is what I meant by “basically zero-cost queue synchronization”. Global queues tend to lead to more balanced systems, but at the cost of constant global queue access. But in grocery store checkouts, that cost is basically zero.

> In the real world you won't have the same service time for both cases since you need to add in walking from the global queue to the individual registers.

In all single-queue systems I've seen, this is solved by the cashier pressing the "register free" button before being finished with the previous customers.

> You will end up with increased confusion from customers who always have to be on the lookout for next open spot

I find it, and I find it pretty clearly, for the opposite to be true. In single-queue system, I can literally sleep-walk and read books/browse social media the entire queue up until the point I reach the front end, where I only need to pay attention to the sign telling me to which register to go. With multiple queues, I feel the need to pay attention to whether or not another register is opening, or whether or not one of the customers in front of me has high handling time risk - so that I can switch queues early on.

Yes, but variance is a thing you want to minimize too, since it forces entrants to be less efficient in allocating their own time since they have to block off more time to cover the n-standard deviations wait-time, which means they can’t be as efficient even if they get the fast queue since they didn’t schedule anything for that time.

It may or may not be worth the extra overhead.

> You will end up with increased confusion from customers who always have to be on the lookout for next open spot

That simply does not happen in the real world.

Many busy supermarkets in SF default to a single line. Trader Joe’s on Market, and Whole Foods on 4th do this. I’ve also seen it at Whole Foods in Manhattan, with reader boards to tell you which check out to go to. Works great!

The reader boards work like a circular buffer. If you pay attention to where the pointer is, you may even jump ahead a few spots by entering the right queue.

Depends on the implementation. In Poland, in all the stores I've seen employing single queue for multiple registers, the board is controlled by cashiers - there's a button at the register that the cashier can press when they're ready for the next customer, and the board always displays the number of the register that signaled readiness most recently.

>Basically zero-cost queue synchronization and heavily variable server time means a global queue is better!

And this is why I always pick the global queue for self-checkout kiosks.

I always hated that "oops I picked the wrong damn line" realization. At that point, it feels too late. It's way better if there's a single line and the cashiers shift the next person off the queue as soon as they are done handling their current person. Although, maybe psychologically it feels better for customers to have multiple lines to choose from?

It feels like a global queue might be unwieldy space-wise if a store's layout wasn't designed for it.

This is getting better with self checkouts which tend to use a single Queue.

The only grocery store I knew that used it is the Whole foods on Harrison in SF. Technically they have 2 global lines/queues for some reason. (Pro-Tip the inside line is shorter because of the single turn in the line)

Those self checkouts are curious. Many people seem to take longer compared to traditional cashier line, but still prefer them. Maybe the same is true for me, although I feel I'm fast...

Perhaps it's something similar like with car vs airplane safety perception. Cars feel safe. Even though planes are extremely safe in reality, you are in control of your own car. Like you're at control in a self-checkout line.

A decent checker usually has the codes for produce memorized, and are much faster than someone looking them up once a week or so. However, I have had some extremely bad checkers that I know I could self checkout faster than. Don't get me started on a bad sacker.

That also makes me think about just how slow the self checkout systems are. The constant yelling out the price of the items I just scanned for confirmation just takes too long. I have to wait for it to stop to proceed. Also, how many times are the systems getting confused about whether you actually put the item in the bagging area or not requiring an attendant to be notified? UGH! </rant> The UI/UX people really need to fix this.

My local grocer has normal lanes with separate lines, express lanes with 6 checkers but a global queue, and the self checkout with a global queue. It seems like it is the family shoppers doing one huge weekly store trip in the normal lanes. Everyone else is looking to avoid them in the other two options.

Self-checkout situation is weird. Since there are no impulse-buying shelves in the checkout area, the store doesn't really benefit from people hanging around the machines. Which leads me to the conclusion that the piss-poor self-checkout UX, where you have to wait on the machine and can't really become a power user over time, must be either cluelessness of the manufacturers, or sabotage.

> Many people seem to take longer compared to traditional cashier line, but still prefer them.

Come to think of it, I mainly self checkout because I don't want to deal with another human.

I mean, the cashiers at the supermarket are very friendly and all, but... I just can't deal with small talk.

After working a checkout counter for a couple years as a teen, I cringe when I see how slow self-checkout makes you scan your items :(

Not where I live - the scanner is as fast as it should be. One shop used to have two cashiers, now it has four self-checkouts and one cashier (I go there if I have some item that needs to be weighted and I haven't already done that by myself earlier. I also go there if the cashier has no customers and looks bored.. :-) It's definitely better and faster than before. My only gripe is that there's limited space for items, so it limits how much I can bring through there.

Target overhauled their self checkout system a year or so ago and it's much better. You can scan items as fast as the cashier at a standard checkout would. When I'm at a different store that uses the old "please place item in the bagging area" system it's like stepping backwards in time.

Agreed. But I have experienced self-checkout setups that just replaced a normal station with a single self-checkout station, replicating the old behavior. These are being phased out near me.

We are already getting the global queue with self checkout, though.

Well designed self checkouts. There are poorly designed self checkouts which replicate the same old structure. They are bad.

I experienced a new thing at the QFC at U Village in Seattle the other day. You grab a little handheld scanner on your way in, enter your customer number, and just scan stuff as you put it in your bag which is in your basket. Then you go to the self-checkout machine at the end, weigh the few things that need weighing, and pay. It's pretty fun!

I haven’t tried this. From what I’ve seen, it doesn’t seem much faster than checking out the normal way. I don’t think it will be around much longer if usage at my local (downtown Bellevue) QFC is any indication.

I’ve also seen this at the Wal-Mart in Mountain View - definitely a cool idea.

who goes to a grocery store anymore? :) I just get mine delivered online. Though I have noticed that many stores( in New Zealand ) have global lines. Also with many grocery stores they have 3 independent ways of getting groceries, the classic find a Q you think is best to get a checkout person. Join a global Q for 12 items or less, or join a global Q for self checkout.

Where I live it would cost a fortune to get grocery produce delivered to my home. Alternatively I could drive all the way to the post office.. which happens to be where there are lots of grocery stores anyway. And if I need milk or cream today, then there's not much help in ordering online.. it would take days. So I think I'll continue to limit my online shopping to electronic parts and the like.

I thought it hardly took any extra charges to deliver to your address, atleast that's how it is in my country, only it might take about a day, since the home delivery grocers run a route and deliver to you as per their schedule though you can choose among the available slots.

Ok you meant delivery directly from the grocery store.. in that case, that's how it used to be in the distant past - you could call in, and they would send their driver with the grocery. The last shop that did that kept the practice up for their elderly customers (and only those) for some additional years, but then eventually had to stop. It's way too expensive to pay a driver to do that.

Online grocery shopping seems to be how stores ditch their lowest quality products. The produce is always on the verge of spoiling. You get the worst cut of meat, etc. And you pay extra for it. I never use it anymore.

I would think this doesn't matter for most of the things. Meat cuts maybe, but otherwise, the "best before" dates always seem tuned to maximize waste of perfectly good items, and with on-line shopping at least you won't end up participating in the silly game of "I won't buy anything that looks more than one sigma away from perfection".

> who goes to a grocery store anymore?

Oh you know, just most people? ;)

Why just US? I think that's pretty universal, at least in most western countries.

I don't have much firsthand knowledge of grocery stores outside the US, so I didn't want to over-generalize.

Costco is fantastic at everything...except the checkout process.

So should I leave space on the highway so my lowest speed through the occasional slowdown is higher than average or am I hurting the traffic flow?

I recall reading about (highway) traffic being a queuing problem where the arrival rate exceeded the clearance rate due to a transient action (someone tapping their brakes because they were distracted or a bright glint from a glass truck going the other way). If you decrease the arrival rate slightly such that the clearance rate can remove the stopped/slowed cars then the entire traffic flow will return to the norm for the volume of traffic on the road.

Sound? Valid?

Stop/go is bad. Gliding is better for the collective and for your fuel efficiency.

CGP Grey has a great video on traffic flow: https://www.youtube.com/watch?v=iHzzSao6ypE

They do this in the UK with variable speed limits, the M25 (ring road around London) is the bottleneck so you will regularly find that the roads joining it during rush hour will have a limit when there is no apparent problem.

If the drivers are rational then going at the average speed works best.

But in real life people would cut you off making you slam the breaks and making the problem worse.

Brakelights lead to brakelights which leads to parking lots on the highway. Most people really only need to let off the throttle and coast, but its either throttle or braking for some people while driving.

There is an excellent youtube video on this (won't be able to look it up until later) but researchers had people drive at constant speed in a circle in a parking lot. Little by little, people bunched closer and closer, and once people started hitting brake lights it became stop and go. With 12 people driving in a small circle.

Capacity should be proportional to speed over car-distance. I wonder if mitigating ripples can really overcome that much increased distance.

Shouldn't it be proportional to sqrt of that, or something else that's sublinear? In places where people have respect for law and safety of themselves and other human beings, the distance between cars should increase with speed.

Braking or a quick lane change causing traffic jams is a well known and refuted myth. Similar to the idea that driving slower on the highway is more dangerous. We have massive amounts of data on both of those. I wouldn't put too much value in that source.

And that would be my fault - my parenthetical was just imagined reasons why there might be a saturation-related slow down.

In trying to look for the source I did come across [1] from a few years ago and may have been remembered incorrectly.

Edit: More details at [2], [3], and [4] some noting transient braking may be a factor.

[1]: https://www.npr.org/2013/11/29/247825768/phantom-traffic-jam...

[2]: https://www.vox.com/2014/11/24/7276027/traffic-jam [3]: http://math.mit.edu/projects/traffic/ [4]: https://www.sciencedaily.com/releases/2007/12/071219103102.h...

Right, those are brief disruptions that cause no significant variation in total transit times.

Much like the idea that slower drivers cause more accidents, this is based on other drivers experiencing discomfort and having to be more careful to avoid the slower car. It feels like it is more dangerous, but the data we have shows that it does not result in more accidents.

Traffic jams that cause meaningful changes to total transit time are almost always based upon significant disruption events(accidents) or uneven capacity(merging traffic at a higher rate than the freeway can absorb).

We know from psychology that a person will perceive something that requires more attention and effort as taking longer and perceive something that requires less attention and effort as taking less time, even if the times are equal.

You are continuing to make assertions without references.

My experience of traffic jams is that they are normally caused by density of traffic. There are a lot of simulations out there that show how small variance in high density traffic acts like a wave that propagates backwards. You even see it on escalators on the tube here in London, where people are supposed to walk on the left but often get stuck in a standing state at busy rush hour times.

http://www.traffic-simulation.de/ring.html is a good one - push up the density and see how the wave propagates backwards. It's not merging that causes the problem, it's density.

Of course standstill traffic that stops everything for minutes at a time is usually something else. But that isn't an everyday jam. And everyday jams do make a meaningful difference in transit time. They even affect me on my motorcycle especially as roads get narrower to accommodate bicycle lanes. I do however still get through and it's a rare day that there is any kind of event or interesting artifact at the front of the jam.

> Much like the idea that slower drivers cause more accidents

Slower vehicles are more likely to end up in an accident. Speed - accident rate curve is IIRC called Solomon curve. I haven't heard this theory disproved.

> this is based on other drivers experiencing discomfort and having to be more careful to avoid the slower car

I have heard experts saying that observations indicate that slower drivers cause accidents indirectly. They are usually slow enough to irritate other drivers, but fast enough to make it hard for an average car to overtake them safely, which pushes some faster drivers into dangerous situations, sometimes resulting in accidents from which the slower drivers escape unscratched.

> Much like the idea that slower drivers cause more accidents

I think this might be statistically valid, due to correlation with the root cause. Drivers who are inexperienced or uncomfortable due to poor eyesight, poor reflexes, unfamiliarity with the vehicle or area naturally slow down.

These are the same sorts of “driver disadvantages” that would cause more accidents.

No references, just intuition based on decades driving in Chicago traffic.

Can you cite some sources supporting your statement or providing analysis of the massive amounts of data you mention?

Some goodies via Jon Bentley:


And a different presentation of some of the same material, on consequences of Little's Law, from his book Programming Pearls, quoted here: http://www.cs.fsu.edu/~baker/opsys/notes/queueing.html

(I'll paste this here as it's already being shared online)

"For instance, if you're in line waiting to get into a popular nightspot, you might figure out how long you'll have to wait by standing there for a while and trying to estimate the rate at which people are entering. With Little's Law, though, you could reason, `This place holds about 60 people, and the average Joe will be in there about 3 hours, so we're entering at the rate of about 20 people an hour. The line has 20 people in it, so that means we'll wait about an hour."

Bentley also cites the following, attributing them to Peter Denning:

"The average number of objects in a queue is the product of the entry rate and the average holding time."

"I have 150 cases of wine in my basement and I consume (and purchase) 25 cases per year. How long do I hold each case? Little's Law tells me to divide 150 cases by 25 cases/year, which gives 6 years per case."

"The response-time formula for a multi-user system can be proved using Little's Law and flow balance. Assume n users of average think time z are connected to an arbitrary system with response time r. Each user cycles between thinking and waiting-for-response, so the total number of jobs in the meta-system (consisting of users and the computer system) is fixed at n. If you cut the path from the system's output to the users, you see a meta-system with average load n, average response time z+r, and throughput x (measured in jobs per time unit). Little's Law says n = x*(z+r), and solving for r gives r = n/x - z."

Tangential: in the article submitted the other day[0] that interviewed Japanese demoscener 0x4015, he brought up a time-lapse video of half a million people queueing for an event in Tokyo:

> I should also mention Comic Market (Comiket). It’s the world’s largest self-published manga exhibition & sale fair, and about half a million people (back then, quarter-million) visit there. This is a time-lapse video of the queue for the Comiket entrance. It gets demo-ish after 40 seconds and I find it interesting.

It is oddly mesmerizing to watch, indeed[1].

[0] https://news.ycombinator.com/item?id=18965767

[1] https://www.youtube.com/watch?v=ermNqkUUiJw

Vaguely on the topic of queing I noticed this year on black Friday several sites had queue systems ( e.g 'game' store was one I remember and even had a limited time you could spend on the site after the queue ).

Part of me wonders whether this was really a server capacity issue or there was some sort of psychological gaming scheme for customers to feel like they need to make a commitment to purchase.

Does anyone have some information on this sort of tactic if so?

If this wasn't a gaming scheme, it soon will be. I bet it worked.

Two large Australian department stores implemented single global queueing for non-self-serve when they introduced self-serve. Its a mixed bag because they also reduced staff on the line to match maximal delay for minimum fuss: ie, they don't aim to serve this line any faster than the worst-case single line instance.

It doesn't invalidate the single global line theory: it points out that the qui bono moment in a queue is not you the customer: its the profit centre. They do anything to maximise profit absent a strong signal they went too far.

its morally akin to basic time-and-motion/taylorism.

The signal I usually give is that when I arrive at a line of (understaffed) counters, with all of them having long queues, I turn around with my basket or cart, put everything back on the shelves, and leave. I do that if I it's clear that I have to wait more than a few minutes.

The signal is clearer if you abandon the trolley and walk out.

It’s interesting that all the grocery stores with automated checkouts I’ve been to have single lines for multiple automated checkouts, but multiple lines/single servers for human checkouts.

that happens a lot at grocery stores because of carts. it’s even more obvious at costco.

stores where people are more likely to hold items in their hand or a small basket can do global queue like home goods or old navy. but once you have 10-40 carts lined up it’s a shit show. imagine costco on the weekend with everyone trying to push their cart through a maze of switchbacks.

self checkout likely has less carts through it than staffed chashier lines. also their close grouping makes this a little less of an issue

Queuing theory is something I'm familiar with from my educational background and general interest in math and systems. But I don't actually know of a good introduction to the topic, it's just a set of information I've accumulated and internalized over the years. Any suggestions from the HN crowd for something I can pass around to some of my team leads and managers that will help them to understand these topics?

+1 For the above mentioned book, especially if you are looking at computer systems/networks.

For more pragmatic treatment found "Fundamentals of Queueing Theory"[1] really good.

[1] http://mason.gmu.edu/~jshortle/fqt5th.html

Related: Stochastic Transport in Complex Systems

Ant trails, traffic jams, ...


Thank you for asking! Queueing theory is a topic I was completely unaware of despite a few years of CS in university. It seems like such a fundamental and useful model for just about anything in software and computing.

We've gone to great lengths to get as close to accurate 'queueing theory' for our game, SimAirport. The systems allow for a global queue for many desks, or one queue per desk, or any hybrid of one queue per N desks, etc...

It's tough because scaling time & 'movement distance' in a simulation game isn't easy -- but sounds like that's actually an issue in real-life, too. :)

I was expecting them to explain why the queue I join is always the slowest.

You're probably joking, but you have spent more time overall in slow queues than you did in fast queues... This is similar to the fact that "your friends have more friends than you do" [0]

[0] https://en.wikipedia.org/wiki/Friendship_paradox

My rubric for picking the quickest queue is the one with the lowest total age. A queue of pensioners will take longer to pack bags, find the right payment card, redeem vouchers and chat with the cashier.

Also tourists and people with many products in their vicinity. Suddenly I really want to collect numbers of this. What's the proportion of age to product count, for example? How many tourists are one pensioner?

Beautiful! Actually very realistic except the end.

It isn’t, but it can easily appear to be the case because you do spend more time in slower queues (simple example: 2 queues with waiting times of one minute and five minutes give an expected waiting time of three minutes, of which you are expected to spend 2.5 (83% of waiting time) in the slower queue), and almost no time in queues that move so fast that you’re out of them before the waiting starts to annoy you.

Because you stop paying attention to the queues once you're done in them so you're the last person you ever observe being served?

There may be many checkouts but you will be aware of only three: your own and the one on each side. There is only a one in three chance that yours will be quickest, so you usually feel that you've picked wrong.

They did.

Because you're buying ice cream.

Is there a nice and visual queueing theory simulator for python or other programming language?

I had written a quick visual demo using the Python mode of Processing language. Perhaps someone here can build upon it.


There is also a rough application of some queueing theory ideas (one might also say, the more general lessons one sees in the physics of transport phenomena, before one specializes in continuums etc) to business, called "theory of constraints." The basic idea is that there is probably right now only a handful of things that are slowing down your ability to make more money, and if you can figure out what they are and add extra capacity to those things, you can presumably get "more bang for your buck" than attempts to improve every part of the system individually. A lot of authors also discuss similar concepts under "systems thinking."

More specifically, the theory of constraints is kind of half-applied to the "projects" contexts that we work in in software in the "critical chain" methodology. It basically says in our context that for each project you have, at any given point during a sprint, there should be one person who is "holding the baton" for that project, they need to be aware that any delays in their work are getting communicated to the project launch date, while others working in parallel are usually exempt. Essentially exactly one person on the project should be panicking, and everyone else should have spare capacity to handle the routine "hey Alice from HR wants us to change all of the articles in the table which Bob has authored so that they no longer say that they were authored by Bob since his last day is next Friday, can someone write SQL to do that?" -- even if Carol has the most domain knowledge about that, if she's holding some other baton, that comes first. In fact, if Carol can split her work -- one common one in our field would be between functionality and tests/documentation -- so that she can pass the baton a little sooner, often that is a net win, too: she finishes the core functionality up to testing-by-hand, she delivers it to Darryl who is the next to hold the baton, then she documents and adds unit tests in a separate PR before she loses her context about it.

Similarly the management of these projects is different because you don't want to estimate "hey Carol we think this is a two-day PR and we will hassle you come day three," since if she judges it to be a half-day PR then it's in her best interests to spend a week on other urgent-seeming requests as those minimize who is hassling her. But instead you want to communicate "hey, this is going to take however long it takes, and I know I cannot make it happen faster by hassling you. I want you to know that even though we guessed that this was a within-one-day task we put an extra safety cushion in the project in case it goes longer, but you have the entire project's safety cushion if you ultimately need it: conversely, any time you save right now can be passed on to your other developers. What I need from you is a daily guess about when you realistically think you can pass that baton so that I can tell Darryl, 'hey, heads up, you're about to have to drop everything and pick up this baton.' You can change that estimate at any time, I just want to minimize that friction and encourage you to sprint as hard as you can on this since you're on the critical path, if anyone tries to tell you that they have something more important for you to be doing, you tell them to talk to me and I will do it personally."

Also the queueing theory makes me a lot more patient with myself. Like I used to get really hard on myself about how "you spent all of this time on the job doing this other thing that didn't need to get done, you lazy procrastinator you!" ... with some queueing theory you start to ask, "what would happen if we defined load as the maximum usage of CPU, RAM, network -- what would happen if we ran a server at 100% load? Machine failure, yes... but also high latency, and things would just get dropped forever. So what would happen if I run myself at 100% load, is that really what's best for the company?" and in a couple of cases (like on these critical paths, with a crucial deadline) that is what's best for the company, but in most cases actually the company should want you to have some idle bandwidth so that you can promptly serve their ad-hoc needs.

s/spend a week/spend a day/

Apparently I am trying to edit this after some threshold time...

Interesting Freakonomics episode [0] about this, where among other things they suggest that the most efficient queue puts newcomers at the front, essentially LIFO... thus transforming the queue to a stack!

[0]: http://freakonomics.com/podcast/what-are-you-waiting-for/

But only if all the players are rational. :)

And then there’s how they wait in line in Cuba...


> With only one teller, customers will have to wait nearly five hours on average before they are served. But if you add a second teller, the average waiting time is not just cut in half; it goes down to about 3 minutes. The waiting time is reduced by a factor of 93x.

This is exactly why asynchronous programming (where every task competes for the same CPU) is such a bad idea.

I don't see what this has to do with asynchronous or synchronous programming. If you have more work to do than what the core can handle, you're going to wait a while no matter what style of programming you use.

The point is that the async style of programming will introduce unpredictable and potentially wildly varying service times. Contrast this to multithreaded programming, where the program is cut into thin time-slices which all have a similar, predictable duration.

I'm not sure I follow... If I understand the async style correctly, the idea is that a task will yield the CPU as soon as it is about to wait for I/O an insignificant time. This allows CPU bound tasks to race to idle, and prevents context switches unless they are nearly certain to be needed.

I guess I understand your concern in the case of multiples tasks that are very CPU heavy, but that hardly seems like a universal issue.

I also think it's a bit of a mathematical sleight of hand to use measures very sensitive to outliers with a distribution that generates large outliers in order to make a point. Perhaps the median or the 95th percentile is more useful. But less dramatic.

Average and variance are different things, though.

I wonder if a noble goal for queuing systems would be to eradicate the need for the queue all together. E.g. more frequent public transport, designated security screening times at airports and gigs, supermarket checkout without tills or home delivery as an alternative. Theoretically it would be nice, but could it be ever be practical...

besides self service cashiers i saw here in Europe global queues implemented only in Kaufland hypermarket, they actually don't use one big global queue but have queues assigned to group maybe of 4 cashiers max., in the end anything it's better than waiting at one cashier queue

Are there any good reads about matchmaking in video games? Which is basically the same queueing theory

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact