ROUTING AND SCHEDULING IN HETEROGENEOUS SYSTEMS - A SAMPLE PATH APPROACH

Consider the problem of routing customers to a set of K parallel serve rs that have different rates. Each server has a buffer with infinite c apacity. The arrival process is general and the service times are assu med to be i.i.d. exponential random variables. Using sample path argum ents, we show that, given any Bernoulli policy pi, there exists anothe r policy rho which outperforms pi by partially using a randomized vers ion of a round-robin policy. Moreover, rho is easily specified and imp lemented. We present extensions of our results to systems with finite capacities and service times that have an increasing hazard rate. Fina lly a similar result is shown to hold in the context of scheduling cus tomers from a set of K parallel queues.