Don't you hate it when you are standing at the end of a long line at the bank when all you need to do is make a 30 second deposit? It has been proven that the queuing algorithm that minimizes average response time is the SRPT, or shortest remaining processing time, algorithm. This should be applied to supermarket lines, bank lines, etc. To get in line, you would have to submit your estimate for the amount of time it will take for you to complete your task. In exchange you receive a number. Then the number of the person with the shortest amount of time is called and that person gets to check out groceries, speak to a teller, etc. This would also encourage people to get done as quickly as possible so they can get serviced sooner. To make sure people don't cheat by giving estimates that are too short, once the amount of time you estimated passes, you are penalized, perhaps getting sent to the end of the line, or having to pay a fine. Also, if someone is taking a really long time at the front of the line, they should be preempted in favor of someone who has a shorter remaining processing time. True, this sounds unfair to the people who have long processing times, but it will greatly benefit the majority of people in line. This algorithm should work especially well for heavy-tail distributions (i.e. a large percentage of the processing time is spent on a small percentage of very time-consuming tasks).

Mor Harchol-Balter wrote a number of papers on the efficiency of SRPT scheduling under heavy-tailed load distributions: http://www.cs.cmu.edu/~harchol/
-- gjlee, Apr 04 2001

In a similar vein http://www.halfbake.../ATM_20Time_20Limit
Much less informative, but a bit more amusing. [absterge, Apr 04 2001, last modified Oct 04 2004]

Queueing http://www.halfbakery.com/idea/queueing
Another time-based queueing idea for supermarkets. [Aristotle, Apr 04 2001, last modified Oct 04 2004]

Interesting, gjlee. I'd sort of worked out for myself (while waiting in line) that SRPT queuing would be the best use of the time of all users in aggregate, though I didn't know it had a name, and I certainly didn't apply enough rigor to arrive at a proof. The problem I kept coming up with, though, is that if the grocery store were sufficiently full of patrons with only a handful of items, the poor shopper with 77 items might *never* get through.
-- beauxeault, Apr 04 2001


Supermarket queues are a special case as all the information needed to determine which queue to join is available (in trolleys and on the belt). To help RodsTiger, each checkout should have a real-time items/second display positioned above the checkout to allow you to use both length of queue and checkout operator efficiency in your calculations.
-- hippo, Apr 04 2001


well, what for might he be buying 77 items at prime-time (I'd guess that at 5pm-7pm Friday/Monday)? That 'poor' shopper would get through eventually (if the store were 24 hour), and the exasperation might just make him a more conscientious shopper in the future.
-- absterge, Apr 04 2001


Yeah, there seems to be a problem with the fact that this will change the behaviour of the folks in the queue because of the relegation of big shoppers to the end. The most efficient and least aggravating way to do one's shopping (and soon, the only possible way) would be one item at a time, resulting in a lot of frictional time losses and worse overall performance. There's also not much of an incentive for supermarkets and others to start making their biggest customers wait the longest. And note that the existence of x-items-or-less (yes, we know) probably counts as a fractional baking.
-- Monkfish, Apr 06 2001


Heck, why don't we make old or handicapped people wait longer as well, since they take more time?

Distributional issues aside, the problem is that utility is not a linear function of time. How about an algorithm that minimizes the square of the response time?
-- bookworm, Apr 06 2001



random, halfbakery