Multichannel Scheduling and Its Connection to Queueing Network Control Problem
The authors consider the multichannel scheduling problem where the data rate offered by a channel is heterogeneous across users and the transmission time of a packet is random. The objective is to schedule the transmissions of all users over multiple channels to maximize the average weighted throughput of the network. Based on a Markov Decision Process formulation, they show that this problem is in general EXP-hard. To obtain computable performance benchmarks, they consider preemptive policies as well as the saturation mode in which a simple polynomial time algorithm is shown to be optimal. Both lead to upper bounds for the original problem.