Queueing theory: The science of waiting in line
johndcook.com
johndcook.com
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)
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.
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.
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.
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.
You may read that as you please.
"This isn't rocket science bro. Obviously more lines = faster."
You can have your cake and eat it too, it turns out.
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
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.
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.
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.
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.
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.
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.
Multiple lines in western Washington, FWIW.
It's absurd. Works pretty well though!
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.
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.
As for self checkout lines there should be a huge sign that asks "are you prepared for this technology?, Really? Are you sure?"
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.
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.
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?
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.
It may or may not be worth the extra overhead.
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.
That simply does not happen in the real world.
Oh you know, just most people? ;)
And this is why I always pick the global queue for self-checkout kiosks.
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.)
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?
But in real life people would cut you off making you slam the breaks and making the problem worse.
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...
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.
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.
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.
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.
CGP Grey has a great video on traffic flow: https://www.youtube.com/watch?v=iHzzSao6ypE
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.
http://www.eecs.harvard.edu/~margo/cs261/background/p176-ben...
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."
> 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].
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?
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.
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
For more pragmatic treatment found "Fundamentals of Queueing Theory"[1] really good.
Ant trails, traffic jams, ...
https://www.elsevier.com/books/stochastic-transport-in-compl...
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. :)
Because you're buying ice cream.
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.
Apparently I am trying to edit this after some threshold time...
[0]: http://freakonomics.com/podcast/what-are-you-waiting-for/
https://www.washingtonpost.com/world/the_americas/in-an-onli...
This is exactly why asynchronous programming (where every task competes for the same CPU) is such a bad idea.
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.