IEEE Transactions on Automatic Control, Vol.40, No.1, 156-161, 1995
Routing and Scheduling in Heterogeneous Systems - A Sample Path Approach
Consider the problem of routing customers to a set of K parallel servers that have different rates. Each server has a buffer with infinite capacity. The arrival process is general and the service times are assumed to be i.i.d. exponential random variables. Using sample path arguments, we show that, given any Bernoulli policy pi, there exists another policy rho which outperforms pi by partially using a randomized version of a round-robin policy. Moreover, rho is easily specified and implemented. We present extensions of our results to systems with finite capacities and service times that have an increasing hazard rate. Finally a similar result is shown to hold in the context of scheduling customers from a set of K parallel queues.
Keywords:PARALLEL SERVERS;QUEUING-SYSTEMS