Server allocation and routing in homogeneous queues with switching penalties

Abstract

This paper considers a multiclass routing and server allocation problem in a queueing system of multiple stations in parallel with penalties for switching the server between stations. We proceed by dynamically ranking the queues so that if all arrivals ceased, switches of the server between queues would be maximally delayed by serving queues in order of rank. The main result of this paper shows that we may improve any policy by constructing a greedy version that routes arriving customers to the queue of highest acceptable rank and allocates the server to the queue of highest rank whenever it switches. We also establish analogous results for a variant of the problem that encourages fairness in server allocation by restricting attention to pseudocyclic policies which visit each queue periodically. © 1996 IEEE.