SRPT queuing

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/