Multichannel scheduling and its connection to queueing network control problem

We 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, we show that this problem is in general EXP-hard. To obtain computable performance benchmarks, we 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. Low complexity approximation methods are then developed to achieve efficient solutions. Furthermore by drawing a connection to the queueing network control problem which is known to be EXP-complete, we obtain sufficient conditions under which the complexity of the queueing network control problem is reduced to polynomial-time.