How? Are they processing more units from the queue per second? Is it easier to find the vague end of a line among a jumble of people than the head of a queue? Are LIFO queues more likely to have something in them than FIFO queues thus avoiding wait times for the next customer and idle staff? Is it a good idea to leave a large portion of boarding to the last few minutes of the boarding interval?
There's probably also a pareto equilibrium illusion going on. If you screw the one person at the bottom of the stack, but serve everyone else more efficiency, is that 'the best choice'? Indeed, there may be no way to rearrange the order of service so that no one is worse off, but that is not necessarily the 'correct' optimal.
I've often thought that the root of many queues is a discontinuity in pricing. This is most apparent on black friday. If prices were smoothed out then a time/money trade-off can happen. Anyone can jump to the front of the line if they are willing to pay more. This is more "fair" than last first but would optimize revenue for the seller, and lower wait times for everyone.
Imagine: The next iPhone sale stars at $10,000. The crowd makes a loose circle as the clock starts to count down to sale time. Just before the clocks reaches zero, one obviously rich and important individual struts up to buy one. They casually complete their transaction, and hold up their prize as the clock starts counting down from 30 again.
At time=zero, the current price starts dropping $5 per second until about a minute later the next person is willing to step up to buy it for $6k. They walk away satisfied because of the conspicuous consumption they have just experienced. Several more step up as the price begins dropping again at $4k, $3750, and $3100. The envy of the crowd is palpable.
At $2560 a small swarm of early adopters breaks ranks. It's a good 20 minutes before the price starts dropping again. As you watch the large pile dwindle and the crowd begins to vibrate it's clear they will not be reaching the base price today, but will instead sell out the entire inventory at some unknown price.
As you eye the crowd, you think about how much you want it, and suddenly your heart races as you step out in front of everyone else to get your hearts desire.
Or perhaps, you wait around a corner with a rock and you bash the person who bought it at $10k head in.
This is idiotic at best. If a iPhone is worth $10k and it someone's hearts desire. They should get taxed the bajesus out of them and that money spend on actually doing good in society!
I once tried to sell a car like this. I put an ad in the paper that said, say, $6000 and dropped it in price over time. It didn't sell.
Years later when I went to buy a house the real estate agent explained to me why. The market for houses (and presumably cards) include lots of people who are watching and waiting for months or years to buy. They get into a steady state where they only look at new listings and ignore the ones they've already seen.
So if your house or car doesn't sell relatively quickly, you move from the seller-arrival queue to the buyer-arrival queue. Which takes disproportionately longer and it's likely that you won't be getting the best price for it.
The incentives for the real estate agent make them think that way though. If they sell a house for $200,000 in a week, they are probably a lot happier than if they sold it for $300,000 in 6 months.
That's known as a dutch auction and it can be highly effective. I know all about them since wholesale flowers are sold this way (hence the dutch connection) and my brother in law's family is in flowers. It's a very fast form of auction since a single bid wins each lot. Rather than the price being driven up in fits and starts it drops at a steady and fixed rate.
Similar to the article's authors dutch actions improve the average at the expense of the extremes (in this case towards sellers). Dutch actions don't often have the sky high prices some traditional actions can drive rare items to but they tend to sustain high average prices because you must bid without reference to the value someone else may place on the item. A traditional auction you may sneak away with an item for less than you expected if no one bids against you. In a dutch action you will likely pay closer to the maximum price you were willing to spend since the longer the wait the greater the risk someone snaps it up without any recourse.
I hadn't ever thought about a dutch action for highly coveted copies of the same item though. It's very interesting idea that would likely kill much of the launch day line up (especially if preorders were accepted online). If the 100 the store has to sell are the only ones that would ever be the prices would be driven into the stratosphere but if you know you can wait a week or 2 for your preorder to be filled and pay the actual "retail" price that's a strong incentive to stay home and buy it online rather than waiting in line for hours.
It sounds to me like the researchers trials were ignoring the reason queues exist. You dont choose to go to the bank or post office (for example) at an arbitrary time. You go because you have business which must be conducted and you only have certain time windows available in which to go there. The higher the overall demand for service is at this time the bigger the queue will be.
Also in the last served first system it would be possible for people in the bottom of the stack to never be served! As long as a steady stream of newcomers arrived.
In supermarket lines, for example, you let people choose their queue because you can see what people have and let them judge which queue they should be in to incentivise them to go to the queue which packs them in the most. I always feel a bit guilty when I purchase dry ice (for science) at the supermarket because it causes queuers to make an error in judgement as to the length of the line.
At banks and the DMV, because there is no way to judge how long someone in front of you is going to take, it doesn't make sense to let people choose, so there is a single queue that is distributed at the end of the line.
Actually the DMV in my state works a little differently (at all of the secondary businesses which perform that task under some state license system, probably notary of the republic based; I never looked in to the details).
There is generally a queue for a /type/ of operation that you are doing. It's expected that the average time to service a given person receiving that service has only minor variation and an occasional outlying exception.
It seems that there is usually one agent assigned to each queue, and sometimes additional agents are assigned (balanced?) as load dictates.
I can see a lot of cases where someone gets stuck in the queue and is never served. It's quite possibly (and even likely) last in first out provides the lowest average wait time but it would come at the expense of the outliers. First in first out is the standard for lining up with people because it provides the lowest deviation from the average. It's the most fair system for everyone involved because you wait from the back to the front just like everyone else, no special cases.
Optimizing FIFO is easy as well: just go when other people are less likely to be there. There is incentive to shop for christmas Dec 1 since Dec 23 the mall is a mad house. I did my grocery shopping when I worked graveyard shift at 2 AM on my weekend with 24 hr grocery store since the place was deserted. I stroll out for lunch at 11:30 AM and beat the rush at the food trucks. Not everyone has the flexibility to shop at 2 AM or shift lunch time but for those who do there is incentive to take advantage. Optimizing LIFO is also easy but awful for those around you. There is no more incentive to find a low volume time; just rock up and stroll past the suckers who tried to beat the rush but just didn't quite do it.
Some common things people line up for:
Low volume shop (ex furniture) - Here you'd never wait that long to pay simply because there are not that many customers. If the cashier is busy customers simply linger longer around the merchandise and wait for availability. No need to make any changes
High volume shop (ex supermarket) - These stores have a steady stream of customers so would be the most likely to get someone stuck in the queue for a long time. If there is a spike in customer numbers for 1/2 hr but then a very steady stream of shoppers for the rest of the day someone could be waiting hours for the queue to dwindle low enough to clear the spike. The steady stream takes up the full cashier capacity leaving the spike waiting for service while their food spoils. If the rate of customer arrival exceeds cashier volume (as it often does during busy times) some people are going to wait in that queue until the rush subsides.
general admission event - Here people pay the same amount for tickets and in FIFO are able to pay extra with their queuing time (since time is money) to indicate how much a good seat is worth to them. In LIFO you would try to arrive as late as possible but the venue can only be filled so quickly so you'd get the reverse of the stadium emptying problem. When everyone gets up to leave at end the exits become a massive bottleneck and everything slows down. If being late means you skip to the front of the queue everyone will arrive late and the event won't start on time since no one will be in their seats when the event is supposed to begin.
I don't doubt there is some math that would indicate average wait times would go down with FIFO but queueing isn't about minimizing the average, it's about minimizing the extremes. Often minimizing the extremes is at the expense of the average. A O(logn) queue sucks if the worst case is O(n^4). Better to have O(n) and fewer stabbings.
The problem with this method is starvation. If you treat a queue like a stack, and you have a steady stream of incoming people, the first person in the queue will die of starvation before they are helped.
14 comments
[ 3.3 ms ] story [ 44.9 ms ] threadHow? Are they processing more units from the queue per second? Is it easier to find the vague end of a line among a jumble of people than the head of a queue? Are LIFO queues more likely to have something in them than FIFO queues thus avoiding wait times for the next customer and idle staff? Is it a good idea to leave a large portion of boarding to the last few minutes of the boarding interval?
Imagine: The next iPhone sale stars at $10,000. The crowd makes a loose circle as the clock starts to count down to sale time. Just before the clocks reaches zero, one obviously rich and important individual struts up to buy one. They casually complete their transaction, and hold up their prize as the clock starts counting down from 30 again.
At time=zero, the current price starts dropping $5 per second until about a minute later the next person is willing to step up to buy it for $6k. They walk away satisfied because of the conspicuous consumption they have just experienced. Several more step up as the price begins dropping again at $4k, $3750, and $3100. The envy of the crowd is palpable.
At $2560 a small swarm of early adopters breaks ranks. It's a good 20 minutes before the price starts dropping again. As you watch the large pile dwindle and the crowd begins to vibrate it's clear they will not be reaching the base price today, but will instead sell out the entire inventory at some unknown price.
As you eye the crowd, you think about how much you want it, and suddenly your heart races as you step out in front of everyone else to get your hearts desire.
This is idiotic at best. If a iPhone is worth $10k and it someone's hearts desire. They should get taxed the bajesus out of them and that money spend on actually doing good in society!
Years later when I went to buy a house the real estate agent explained to me why. The market for houses (and presumably cards) include lots of people who are watching and waiting for months or years to buy. They get into a steady state where they only look at new listings and ignore the ones they've already seen.
So if your house or car doesn't sell relatively quickly, you move from the seller-arrival queue to the buyer-arrival queue. Which takes disproportionately longer and it's likely that you won't be getting the best price for it.
Similar to the article's authors dutch actions improve the average at the expense of the extremes (in this case towards sellers). Dutch actions don't often have the sky high prices some traditional actions can drive rare items to but they tend to sustain high average prices because you must bid without reference to the value someone else may place on the item. A traditional auction you may sneak away with an item for less than you expected if no one bids against you. In a dutch action you will likely pay closer to the maximum price you were willing to spend since the longer the wait the greater the risk someone snaps it up without any recourse.
I hadn't ever thought about a dutch action for highly coveted copies of the same item though. It's very interesting idea that would likely kill much of the launch day line up (especially if preorders were accepted online). If the 100 the store has to sell are the only ones that would ever be the prices would be driven into the stratosphere but if you know you can wait a week or 2 for your preorder to be filled and pay the actual "retail" price that's a strong incentive to stay home and buy it online rather than waiting in line for hours.
https://en.wikipedia.org/wiki/Dutch_auction
Also in the last served first system it would be possible for people in the bottom of the stack to never be served! As long as a steady stream of newcomers arrived.
In supermarket lines, for example, you let people choose their queue because you can see what people have and let them judge which queue they should be in to incentivise them to go to the queue which packs them in the most. I always feel a bit guilty when I purchase dry ice (for science) at the supermarket because it causes queuers to make an error in judgement as to the length of the line.
At banks and the DMV, because there is no way to judge how long someone in front of you is going to take, it doesn't make sense to let people choose, so there is a single queue that is distributed at the end of the line.
There is generally a queue for a /type/ of operation that you are doing. It's expected that the average time to service a given person receiving that service has only minor variation and an occasional outlying exception.
It seems that there is usually one agent assigned to each queue, and sometimes additional agents are assigned (balanced?) as load dictates.
Optimizing FIFO is easy as well: just go when other people are less likely to be there. There is incentive to shop for christmas Dec 1 since Dec 23 the mall is a mad house. I did my grocery shopping when I worked graveyard shift at 2 AM on my weekend with 24 hr grocery store since the place was deserted. I stroll out for lunch at 11:30 AM and beat the rush at the food trucks. Not everyone has the flexibility to shop at 2 AM or shift lunch time but for those who do there is incentive to take advantage. Optimizing LIFO is also easy but awful for those around you. There is no more incentive to find a low volume time; just rock up and stroll past the suckers who tried to beat the rush but just didn't quite do it.
Some common things people line up for:
Low volume shop (ex furniture) - Here you'd never wait that long to pay simply because there are not that many customers. If the cashier is busy customers simply linger longer around the merchandise and wait for availability. No need to make any changes
High volume shop (ex supermarket) - These stores have a steady stream of customers so would be the most likely to get someone stuck in the queue for a long time. If there is a spike in customer numbers for 1/2 hr but then a very steady stream of shoppers for the rest of the day someone could be waiting hours for the queue to dwindle low enough to clear the spike. The steady stream takes up the full cashier capacity leaving the spike waiting for service while their food spoils. If the rate of customer arrival exceeds cashier volume (as it often does during busy times) some people are going to wait in that queue until the rush subsides.
general admission event - Here people pay the same amount for tickets and in FIFO are able to pay extra with their queuing time (since time is money) to indicate how much a good seat is worth to them. In LIFO you would try to arrive as late as possible but the venue can only be filled so quickly so you'd get the reverse of the stadium emptying problem. When everyone gets up to leave at end the exits become a massive bottleneck and everything slows down. If being late means you skip to the front of the queue everyone will arrive late and the event won't start on time since no one will be in their seats when the event is supposed to begin.
I don't doubt there is some math that would indicate average wait times would go down with FIFO but queueing isn't about minimizing the average, it's about minimizing the extremes. Often minimizing the extremes is at the expense of the average. A O(logn) queue sucks if the worst case is O(n^4). Better to have O(n) and fewer stabbings.