Queueing Theory in Practice

Who hasn't been in the company restaurant at lunch time, the local grocery store at 6PM, or the coffee shop and experienced the queues at the cash registers?

The other day I ended up in an ad-hoc contest in our cafeteria with two colleagues trying to get through the process quickest. What's the best strategy when a new register opens and the operator calls out 'next guest in line please'? Stay in line and let others start a new queue? Move over and hopefully skip to the head of the new queue? This made me think about optimizing queue scheduling. Yep, I'm a #nerd...

According to Wikipedia's Queueing Theory topic queues may be managed using one of a number of scheduling policies:

• First in first out - customers are served one at a time and that the customer who has been waiting the longest is served first. - typically I've been waiting the longest, so move aside!
• Last in first out- the customer with the shortest waiting time will be served first. - what's up with that!
• Processor sharing- Service capacity is shared equally between customers. - this results in a big pile up at the register. avoid this queue!
• Priority- Customers with high priority are served first. -  this one is interesting. Do loyal customers have priority? Or new ones (giving them priority may entice them to return, while loyal customer by definition will return, since they're... loyal customers).
• Shortest job first - The next job to be served is the one with the smallest size. - Ok, person in front of all of us ordering the double-java-chip-skim-soy-latte-frappuchino-with-no-room-for-whipped-cream-and-an-extra-shot-of-espresso... to the back of the queue!
• Preemptive shortest job first - The next job to be served is the one with the original smallest size. - Get your cash/card ready already...
• Shortest remaining processing time - The next job to serve is the one with the smallest remaining processing requirement. - Eh... get your cash/card ready already!

All apps thinkable have already been written. So I've downloaded the Java Modelling Tools for queueing analysis.Next time I go get my soup and salad, I'm coming prepared. That'll shave off at least 2 minutes of waiting time. Unless that one efficient cash register operator has a day off ...

And for the java-chip-at-lunch person I have the following tip. Bring your own whipped cream!