Should the first in a queue be served last?
bbc.com
bbc.com
This changes if you have some uncertainty in the cutoff time -- in the flight example, attendants would close off the gate at some randomly determined time, and latecomers would be able to get great seats -- but they'd also have an excellent chance of missing the flight entirely!
In this case, the thing you're bidding with is how much you're willing to risk missing the flight. If you know that the flight will close at a time uniformly distributed between 10:00 and 10:30 for example, those who arrive at 10:29 are willing to accept a 29/30 risk of missing the flight in exchange for being virtually guaranteed their choice of seats.
Realistically it would have to be done with an interval of boarding. Whether this interval is known to the passengers or not I don't think matter.
So boarding is between 10:00 and 10:30. The first passenger to arrive after boarding starts will be the first to board, since they would be at the end of the line at that time. And so would the next one, and so on.
I think the queue is a pretty good system to use, because it's effectively an auction for a spot at the top of the line, where you pay only with your time. This seems like it would balance incentives reasonably well. Come to think of it, it'd be interesting to see economic auction theory applied to queues.
The purpose of a line is that you have an inconsistent flow rate. If you always had less than one person arriving per minute and it took less than one minute to process one person then there would be no need for ordering the people waiting because there would be no people waiting.
The trouble arises when that isn't what happens. At 10AM there is no line at the lunch counter but by 11AM or noon there are more people looking for food than there is serving capacity, so a line forms and remains until 1PM or 2PM when the rate of new customers has fallen back below serving capacity for long enough to process the backlog.
A queue is inefficient because it causes everyone to wait e.g. 15 minutes during the busy period. If you use a stack instead of a queue then a person who arrived at 11AM and sees the number of people in line in front of them continue to increase will correctly deduce that continuing to wait is futile. They won't be served until ~1PM when the entire backlog is filled, so assuming they aren't allowed to reposition themselves in line immediately, they might as well just leave and come back later. And maybe resolve to get there by 10:45 next time, when demand is lower and everyone is still being served immediately. Which is where the efficiency comes from -- more people arrive either before or after the rush to avoid getting stuck at the bottom of the stack, so the wait time goes down.
The trouble with it is that it lowers the average wait time but it makes the wait time for any particular individual completely unpredictable. You could end up being second to the top of the stack for several hours while everyone else is served immediately.
>A queue is inefficient because it causes everyone to wait e.g. 15 minutes during the busy period. If you use a stack instead of a queue then a person who arrived at 11AM and sees the number of people in line in front of them continue to increase will correctly deduce that continuing to wait is futile. They won't be served until ~1PM when the entire backlog is filled, so assuming they aren't allowed to reposition themselves in line immediately, they might as well just leave and come back later.
Which is a big assumption.
That's exactly what the GP was warning about: people will just go into a different "meta-queue" in which they vie for being the technically-"last" person to enter the real (LIFO) queue [1], with all the externalities that involves. People are still spending time waiting, they just have to do it in a more roundabout way. No free lunch (in money or time).
>And maybe resolve to get there by 10:45 next time, when demand is lower and everyone is still being served immediately. Which is where the efficiency comes from -- more people arrive either before or after the rush to avoid getting stuck at the bottom of the stack, so the wait time goes down.
So ... the entire counterintuitive result is just an artifact of how this method makes it more expensive (in time spent, assuming away the meta-queueing problem above) at peak times? But then it's no different from the case for peak-hour pricing (or the opposite in the case of happy hours and early bird specials).
So it's not that this is somehow more efficient, it's apparently just another way to make peak hour service more miserable. But worse, it does it in a very convoluted way that shifts the entire problem over to "how to game the official record of when I entered the stack".
This whole study seems to confuse a lot more than it clarifies.
[1] which, I know, would no longer be a queue but a stack
The ability of someone to "cut in line" by leaving and then coming back is obviously a critical failing of the system if doing that is cheaper than doing the thing you're desired to do. But you can imagine rules to address it, like if you leave and come back then you get the same position in the stack as if you had never left. (And if this is being implemented in a computer then maybe you get a message on your phone once you're at the top of the stack.)
> So ... the entire counterintuitive result is just an artifact of how this method makes it more expensive (in time spent, assuming away the meta-queueing problem above) at peak times? But then it's no different from the case for peak-hour pricing (or the opposite in the case of happy hours and early bird specials).
It doesn't make it more expensive at peak times. The total cost is exactly the same, but it is imposed highly disproportionately, so that instead of 120 people each waiting 15 minutes, you have 105 people who are served immediately and 15 people who would each have to wait two hours. The theory being that at least some of those 15 people will then give up and leave because they can go do something productive with two hours when they couldn't have with only 15 minutes.
You get essentially the same result by putting a small hard limit on the length of a queue and then banning anyone who showed up when the queue is full from entering the queue until it is completely empty.
Which means you haven't improved the efficiency, you've just shifted it into a different category.
You could do the same by having a bouncer that randomly doesn't let people in. It's not what people think of when they hear "reduced waiting times".
You can construct priority functions to work as a FIFO queue or a LIFO stack if you'd like as well.
One look at the current BBC tech news feed[1] shows a few such disappointing titles.
"VIDEO: Is this the end of ads on mobiles?" "Are we addicted to technology?"
Maybe it's just that I'm 36 and old and crotchety but is anyone else getting tired of reading the "Every Last Thing Western Civilization Thinks Or Does Is Completely Wrong" article? And I don't just mean the "big issues", but, stuff like this article, too. How you queue up... WRONG. How you drink water... WRONG. How you play on the playground... WRONG. How speed limits work... WRONG.
That sentence does not even come close to properly addressing it.
pkaye mentioned one of the critical flaws with the plan, and you quoted the article as if he missed the part where it addressed the flaws. But it doesn't address them, it just says "maybe my plan doesn't make any sense, not my problem".
In any case, I'm just reiterating what the article says about this point, not sure what there was to disagree about.
With normal FIFO queues you're free to abandon your place in line if, for example, you decide it's taking too long and you'd rather do something else. If later the line dies down you're free to go get back in line and you're not being a jerk.
However if you get stuck too far back in the LIFO queue, then it's actually in your best interest to abandon it and come back later. But there's no socially appropriate way to do this.
I think if you tried to do this in the real world it would quickly devolve into a mob. Random order would probably work better.
I suspect the airport would be interested in trying out the LIFO approach in this particular location.
For a long time, the budget airline Ryanair used to seat its planes first-come, first-served style. This meant everyone would stand and queue at the gate immediately, sometimes hours before the flight, just so they could get good seats. Fair enough, if that's what you want. But Ryanair switched to allocated seating over a year ago, and yet people still stand and queue long before the gate opens, even though there's little benefit. Can it be worth it just to get to your assigned seat slightly earlier?
It still doesn't really help, and still creates a situation where people jockey for the earliest position within their group, or try to sneak in during an earlier group's boarding time.
Southwest takes it a step further and puts both a group and a position number within the group and has passengers line up by number, so that the plane boards strictly in that order (i.e., passenger A1 boards, then passenger A2, then passenger A3, etc.).
But the group and position numbers are determined by check-in time, which moves the rush to check-in (and the first few numbers can be purchased outright for a fee).
I will end the year with about 100,000 miles (not as many as some people here, but enough to see some shit as it were) and something about airplane flight seems to drain people of their humanity entirely.
In the airline example, the airline wants passengers to be at the gate before they begin boarding so that they can start looking for missing passengers as early as possible. I think we see this technique most often used by low cost carriers, and this is one of the many ways that they are able to turn aircraft around so quickly.
There's a real-world variation. At some airports people at the terminal go into a bus, which then takes them to a plane. This serves to mix and somewhat invert the queue, since the last people on the bus become the first to enter the plane.
The question I have is, is there a change in the gate queuing behavior between flights that load directly at the gate, vs. one where people first enter a bus?
It's even more obvious when the neighboring gates also use buses.
LIFO minimizes latency and resource usage FIFO maximizes latency and resource usage
What you want to serve, as a queue manager, is the largest amount of requests in the shortest amount of time. Counterintuitively, this means that you absolutely don't want people who wait a long time in line to get served, because if they're willing to wait on hold for 30+ minutes they're willing to badger your agent (the guy answering the phone) for a long time into doing what they want. The result of this is that the queue quickly gets taken over by these long-waiters and everyone else gets delayed massively.
What you want to maximize is requests served/agent time. Requests served is what brings in the money, agent time is money leaving. LIFO, combined with seriously incentivizing agents to make sure calls get resolved faster than $avg - 10% or so, ideally with a pay bonus (people, especially people in low-end jobs, respond very strongly to pay bonuses).
The net result is that complex requests will result in waiting very long in the queue (because agents will throw you back to the queue as soon as they realize what you want is complex or impossible (people wanting things you can't provide are very bad in all respects, very common, and the people requesting them usually have way too much time). "I want to talk to manager" -> just throw him back in the queue). This means complex and impossible queries really, really start taxing the customer's willingness to sacrifice their time. Ideally this would result in the 2-hour-long "pay for me sending a slightly scratched product I bought last week in the US for 5$ less than I could have it in Antarctica, and let me ship it for replacement in < 1week, or I will #$)(!@#%)! 1@#)$&!@)#$ @$#)@& @)$&)#@& you and your entire family you !#@$ (@&@)(#& #)(&@)&@! #)(@#)(@" conversations to just not happen. Normally there's a lot of these, they wear out agents (people being treated badly by customers to the point of crying happened almost daily)
Now you don't quite go for straight LIFO. Firstly a lot of people are offended by it, think it unfair, that sort of thing (and then the costs start mounting). You also don't want pure LIFO because there are customers that you actually want to serve with complex queries, so you start building a complex multi-queue system, but the entrypoint is usually a LIFO queue.
Per call mixed FIFO/LIFO also gives you a good feel for how technical situations are progressing, and still depletes the older queue entries. Any given center can usually be dialed in, by changing the ratio off the top or the bottom of the stack for the next served.
I would imagine dynamic heuristics based on volume and delta volume/period would greatly assist keeping the queues clean.
More to the point, the people who come "too early" are usually trying to get their thing done before some impending deadline.
Global optimizations sometimes don't go over well with individuals, i.e. it doesn't guarantee that a given individual will spend less time in a queue, and that's what ultimately matters to the individual. I could see this working in airports or other places with ushers, but not as a general principle.
[1] http://www.slate.com/articles/arts/everyday_economics/2001/0...
This isn't manipulation, this is pretty much the defined behaviour. In a queue that doesn't close, this is one of only two ways for the person at the front to ever get served. The other way being for that person to be the only person left in the vicinity who wants the thing being queued for.
This also presupposes the venue doesn't want lines. That's a pretty bad assumption for a lot of service industries. Lines mean your venue is popular and serve as advertising.
Someone should implement this in TCP/IP routers and see what happens.
This is all around a much better system than FIFO. Of course LIFO is the fastest on average, but you want there to be a reasonable, predictable bound on how much time an individual can expect to wait. An extension of this policy could be "partially random first come first served", where you just start at the first person in line and flip a coin with probability 0 <= p <= 1 of getting heads, and if you get heads they get served. If you get tails you move to the next person, with the only exception being the last person in line.
In practice, for airports I would prefer to have the people sitting in the back board first. Then you wouldn't have so much congestion from people blocking the aisle while they stuff their bag into the overhead compartment. Also you shouldn't have to sit in your seat longer for the same flight if you bought a first class ticket.
Right, this is generally handled by how we (implicitly) judge queues, not by the average wait, but by the average square of the wait, and penalize extreme wait times that are concentrated on one person.
It's why it's better to have one line feed into multiple clerks rather than each clearly get their own line: because there's the risk of some transaction taking a long time and screwing everyone in that line.
Single-queue avoids that by allowing people to be routed around that clerk. There's no change in the average, but you've avoided major quadratic penalties.
It's also the problem with LIFO: even if you could somehow stop people from leaving their early-entrance spot (!!) to re-enter for a better one, you're still sticking a few people with horrible wait times, which good metrics penalize.
If it was first in, last out it wouldn't be a queue, it would be a stack.
Come on, author, this is literally computer science 101.
And you're right, a Stack is a Comp Sci term. You're assuming this guy is Computer Scientist, which may not be true (most people are not).
No. Queues are, by definition, FIFO. This article is one of the most idiotic pieces of drivel that I've read in a long time. I want my two minutes back.
Your assumption is incorrect.
Do you have an alternate name for these structures of humans? Are you one of those people that considers technical jargon in a narrow field to supersede all broader meaning of a term? I mean, nothing in the article even suggests CS queues...
Depending on what you're optimizing for, and the behaviors of your system (arrival process, task size distribution, number of servers, preemption overhead, etc.), it can be much better to process things in an order other than arrival order.
In particular, FIFO can mean small tasks end up waiting a long time behind large tasks. (Imagine going into a shop that sells sandwiches and pre-packaged salads; you want a salad, and there are 5 people waiting for sandwiches. Should you have to wait until the clerk makes 5 sandwiches before you can get your salad and leave?)
1. https://en.wikipedia.org/wiki/Queueing_theory#Service_discip...
Also works wonders against rich or pseudo-elite bastards thinking they're too important/rich to wait.
Most airports and other venues with predictable queues offer free wifi and power outlets so where's the problem there?
Only in the absence of other methods of organization. If you pay for a better ticket you usually don't have to wait in the same line.
And if you remove the social expectations of lines, there's no big deal about paying other people to do easy but boring tasks or whatnot.
Sitting in line is still a waste of time.
How people spend their time and value it is subjective. Just because you can put a dollar tag to it, doesn't mean the rest of the world does.