2012 journal article

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

COMPUTER COMMUNICATIONS, 35(13), 1626–1638.

By: H. Al-Zubaidy*, I. Lambadaris* & Y. Viniotis n

co-author countries: Canada 🇨🇦 United States of America 🇺🇸
author keywords: Optimal scheduling; Stochastic coupling arguments; Stochastic dominance; Most Balancing algorithms; Random connectivity
Source: Web Of Science
Added: August 6, 2018

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.