Optimal scheduling in multi-server queues with random connectivity and retransmissions

We investigate an optimal scheduling problem in a discrete-time, multiserver system of parallel queues. The servers are connected to the queues in a random fashion and scheduled packets complete service successfully with a given probability. This model is suitable for the study of dynamic packet scheduling problems in wireless systems. We study first a two-server system of two infinite-capacity queues with homogeneous arrival, service and connectivity assumptions. We use coupling arguments to prove that a “Most Balancing” scheduling policy is optimal, in a stochastic ordering sense, for this system. We then consider a finite-capacity, non-homogeneous, multi-server and multi-queue system. We develop a dynamic programming model to determine numerically the scheduling policy that optimizes a range of cost functions, including average total queue sizes. We also compare the performance of the optimal policy to that of a few other policies via simulations.