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".
I quoted the article where it concedes the point. Usually a system is only coherent within a set of assumptions, in this case the assumption is people can't easily rejoin or see their placement. That maybe doesn't hold for physical lines but the example the article goes into is an internet service where people have no control or awareness over their place in line.
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.
There could be a machine that scans a person's boarding pass and assigns them a number. Then everyone is served by their number. And you can't get a different number if you try to scan your boarding pass again.
One thing the article doesn't mention is how this changes the final time to have all people processed. Wouldn't this result in (for example) flights leaving later, if people were in competition to arrive last?
Absolutely, the article presents the problem as trying to minimise the time that an individual wastes in a queue, not the problem of processing all of the people in the shortest time possible.
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.
It does quote "In practice it would be very hard to implement a principle of serving the last in most physical queues where people physically queue up, for example when boarding an airplane. It's simply too difficult to manage for practical reasons."
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?
This experiment has a startling result only because it runs counter to the established method of queueing. If instead of queues we had stacks (last in, first out), we would no doubt see people organize themselves into the stack in such ways that other time-wasting externalities would arise.
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.
Maybe not exactly what you had in mind, but the economics of allocating scarce resources via queues is pretty well-established (and interesting). You might enjoy this read: http://www.jstor.org/stable/724744
> If instead of queues we had stacks (last in, first out), we would no doubt see people organize themselves into the stack in such ways that other time-wasting externalities would arise.
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.
I'm sorry, but none of this is making sense to me.
>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
> 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).
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.
Instead of calculating your costs ahead of time, use a dynamic priority queue to account for any externalities as they occur and then punish or reward those in the queue accordingly.
You can construct priority functions to work as a FIFO queue or a LIFO stack if you'd like as well.
A FIFO queue is essentially like an auction where you use your wait time in order to bid for service -- the highest bidder (longest waiter) wins. LIFO service as proposed here is equivalent to the lowest bidder winning instead, meaning everyone will try to bid zero (or as low as they can).
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.
This seems to result in every plane leaving either empty or delayed.
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.
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.
Wouldn't it be simpler just not to open the queue pool until immediately before the event? And shoo people off if they try to line up nearby. Then you get more or less exactly what this system would create, an unholy shoving scrum at t = 0, without the built in cruelty to safety conscious planners.
Having flown internationally in Europe recently, I can attest that prompting people back to the seated waiting area (over the intercom) ahead of boarding had zero impact on the forty-sixty people super keen to get on board.
I suspect the airport would be interested in trying out the LIFO approach in this particular location.
I don't understand some of the herd mentality at airports.
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?
The variable here is overhead bin space, not seats. People want to board first, regardless of their seating assignment, so that they're assured a space for their probably oversized carry-on luggage.
Transfer buses can also serve as an excellent demonstration of how LIFO boarding would work. People who are eager to stand in front of the line to enter the bus may actually be the last to exit and board the plane.
Jetstar is a budget carrier here in Australia, and they used to have unallocated seating, flying often out of secondary airports. They switched to allocated seating because people would literally race each other across the tarmac to get the good seats... and sometimes even fight over them.
Airlines in the US do this: your printed boarding pass will have a group number on it, and you board when your group's number is called.
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).
In my observation the main problem here is that there is a limited amount of overhead bin space and no enforcement of the rules on carry-on luggage size, which makes getting on the plane perversely important. Hopefully this explains this otherwise strange behavior to you and some of the child comments.
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.
how about have multiple entry points, but only one will open up. so advise that flight will depart from gates A7-A12, then 5 minutes before boarding announce the actual gate.
People like low individual latency, they really don't care about the queue's throughput or the average latency.
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.
Only if people are joining your line out of their want for the service, rather than some external requirement. Nobody likes a popular DMV, for instance. Nobody wants to be there.
unless they're using queue in a non-compsci parlance. i've never heard of being "last in the stack" while "stacking up" for my turn at the counter. this study seems aimed at addressing human systems, not with data structures.
Keep in mind this article is from a British source and they tend to associate the word Queue to mean what Americans call a Line. So when he is saying a 'LIFO Queue' he means a 'LIFO Line'.
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).
"But the researchers experimented with different queuing systems, and when they told volunteer queuers that people would be selected from the queue and served at random, the average wait was reduced."
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.
>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.
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 the queuers have the opportunity to observe the queue before entering the queue then LIFO can't possibly work because why would anyone enter the queue voluntarely first knowing that you'd be served last? So people would end up hovering around the airport gate indefinitely because no one wants to go first.
Easier solution: print out tickets with a vending machine (or link it with a smartphone web app to reduce paper waste) and allow people to SIT or MOVE AWAY without losing their place. Works wonders w/ children (who often enough get bored as fuck, and as result noisy or otherwise disruptive, when forced to wait for longer periods of time with no movement allowed) and old-ish or pregnant persons who simply are physically overwhelmed by having to stand still for longer times.
Also works wonders against rich or pseudo-elite bastards thinking they're too important/rich to wait.
The entire point of a waiting queue is to ensure equality. The plane is going to depart at the specified time and when you're early enough you can grab the best seat so where's the problem?
Most airports and other venues with predictable queues offer free wifi and power outlets so where's the problem there?
I've been noticing a spate of NYT articles lately too that seem to be summed up by "Every Common Sense Thing You Know Is Wrong Because Some Academic Somewhere Ran A Study That Could Be Read That Way." Presumably to be followed up by "Now That Somebody Did Something Different We're Here To Tell You How That Went Wrong, Too".
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.
this particular headline seems fine though - there is a question for which most people have existing opinions about and some rationale for believing so. and then the article engages some of these notions. conversely if this article were to give the answer in the headline right away 'LIFO queues may be more optimal' one could possibly take the reasons presented at face value without understanding (or even seeing) why it is counter intuitive.
I just remembered that Steve Landsburg wrote about this a while ago for Slate, in the context of joggers waiting for water fountains. [1] It always Steck me as one of those "mathematically true but unphysical" results. Yes, if you could jog indefinitely, and if you could prevent "meta queueing", then you could make it so that there would never be a line at the fountain, but that's not a good model of joggers' needs.
This one got me thinking — what would be the optimal way to face a flight boarding line? If there are no incentives (i.e. seats are already assigned), then you're paying with time for no reward. Many people are using a highly suboptimal approach by waiting in line even before the boarding has been announced. I'm glad I just sit with my computer until there is no one in line :)
I do the same, but I believe many people want to be inside ASAP to get their "hand luggage" close.
It happened to me once that there were no space anymore and my bag was quite far away with the crew luggages.
This reminds me of people driving all over the parking lot looking for a close spot, when it would have been quicker to park in the back and walk an extra 15 seconds...
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.
I assume this is intended to be sarcasm? I thought that the article was very interesting, especially in the context of software engineering, even if the word "queue" was used in the colloquial sense (and not the stricter technical meaning used in computing).
Have you never queued up for something, only to have someone in the queue served out of order? A new cashier's register opens up? Or a special consideration for a member of the queue? I remember being served out of order in a queue for an airline ticket (due to my height).
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...
In the context of queueing theory, there are many service disciplines[1] that can be used, which are not necessarily FIFO.
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?)
> It could be open to manipulation, with people leaving the queue and rejoining from the back in order to get served more quickly.
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.
When working at a helpdesk company managing IVR services, one quicly learns :
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.
I came to share a similar experience running the numbers for a tier 1 IP carrier customer service desk.
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.
78 comments
[ 3.6 ms ] story [ 150 ms ] threadThat 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.
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.
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.
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.
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.
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.
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.
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).
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.
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.
Someone should implement this in TCP/IP routers and see what happens.
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?"
1: http://feeds.bbci.co.uk/news/technology/rss.xml
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.
[1] http://www.slate.com/articles/arts/everyday_economics/2001/0...
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...
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.
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.