OPTIMAL ROUTING AND BUFFER ALLOCATION FOR A CLASS OF FINITE-CAPACITY QUEUING-SYSTEMS

We consider the problem of routing jobs to K parallel queues with identical exponential servers and unequal finite buffer capacities. Routing decisions are taken by a controller which has buffering space available to it and may delay routing of a customer to a queue. Using ideas from weak majorization we show that the shortest nonfull queue delayed (SNQD) policy minimizes both the total number of customers in the system at any time and the number of customers that are rejected by that time. The SNQD policy always delays routing decisions as long as all servers are busy. Only when all the buffers at the controller are occupied, then a customer is routed to the queue with the shortest queue length that is not at capacity. Moreover, we show that if a fixed number of buffers is to be distributed among the K queues then the optimal allocation scheme is the one in which the difference between the maximum and minimum queue capacities is minimized, i.e., becomes either 0 or 1.