Interchange Arguments in Stochastic Scheduling.

Abstract

Interchange arguments are applied to establish the optimality of priority list policies in three problems. First, we prove that in a multi-class tandem of two M 1 queues it is always optimal in the second node to serve according to the "c MU" rule. The result holds more generally if the first node is replaced by a multi- class network consisting of M 1 queues with Bernoulli routing. Next, for scheduling a single server in a multi-class node with feedback a simplified proof of Klimov's result is given. From it follows the optimality of the index rule among idling policies for general service time distributions, and among pre-emptive policies when the service time distributions are exponential. Lastly, we consider the problem of minimizing the blocking in a communication link with lossy channels and exponential holding times.