To Wait or Not to Wait: The Power of Scheduling

No one likes waiting in queues. Unfortunately, queues are unavoidable in a stochastic environment. Think about supermarket cashiers instead of an assembly line. At a supermarket cashier, customers arrive randomly, and the number of items in each basket is random. As a result, queues form even when the cashier is only busy 30% of the time. Scheduling is powerful in reducing the checkout time, both in a supermarket and in cloud computing, except in the latter, questions such as “what if you can’t peek in each basket and estimate how long it will take?” and “what if the checkout time for each basket-cashier pair varies?” have to be answered. In important cloud computing applications, it turns out waiting actually speeds up the process for everyone.