Delay-Optimal Server Allocation in Multiqueue Multiserver Systems With Time-Varying Connectivities

This paper considers the problem of optimal server allocation in a time-slotted system with N statistically symmetric queues and K servers when the arrivals and channels are stochastic and time-varying. In this setting, we identify two classes of "desirable" policies with potentially competing goals of maximizing instantaneous throughput versus balancing the load. Via an example, we show that these goals, in general, can be incompatible, implying an empty intersection between the two classes of policies. On the other hand, we establish the existence of a policy achieving both goals when the connectivities between each queue and each server are random and either "ON" or "OFF". We use dynamic programming (DP) and properties of the value function to establish the delay optimality of a policy, which, at each time-slot, simultaneously maximizes the instantaneous throughput and balances the queues.