  Queuing systems with redundant requests have drawn great attention because of
their promise to reduce the job completion time and variability. Despite a
large body of work on the topic, we are still far from fully understanding the
benefits of redundancy in practice. We here take one step towards practical
systems by studying queuing systems with bi-modal job service time
distribution. Such distributions have been observed in practice, as can be seen
in, e.g., Google cluster traces. We develop an analogy to a classical urns and
balls problem, and use it to study the queuing time performance of two
non-adaptive classical scheduling policies: random and round-robin. We
introduce new performance indicators in the analogous model, and argue that
they are good predictors of the queuing time in non-adaptive scheduling
policies. We then propose a non-adaptive scheduling policy that is based on
combinatorial designs, and show that it has better performance indicators.
Simulations confirm that the proposed scheduling policy, as the performance
indicators suggest, reduces the queuing times compared to random and
round-robin scheduling.
