Dynamic Server Allocation for Queueing Networks with Flexible Servers

This paper is concerned with the design of dynamic server assignment policies that maximize the capacity of queueing networks with flexible servers. Flexibility here means that each server may be capable of performing service at several different classes in the network. We assume that the interarrival times and the service times are independent and identically distributed, and that routing is probabilistic. We also allow for server switching times, which we assume to be independent and identically distributed. We deduce the value of a tight upper bound on the achievable capacity by equating the capacity of the queueing network model with that of a limiting deterministic fluid model. The maximal capacity of the deterministic model is given by the solution to a linear programming problem that also provides optimal allocations of servers to classes. We construct particular server assignment policies, called generalized round-robin policies, that guarantee that the capacity of the queueing network will be arbitrarily close to the computed upper bound. The performance of such policies is studied using numerical examples.