Interchange arguments in stochastic scheduling

Interchange arguments are applied to establish the optimality of priority list policies in three problems. First, the authors prove that in a multiclass tandem of two ë/M/1 queues it is always optimal in the second node to serve according to the cμ rule. The result holds more generally if the first node is replaced by a multiclass network consisting of ë/M/1 queues with Bernoulli routing. Next, for scheduling a single server in a multiclass 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, the authors consider the problem of minimizing the blocking in a communication link with lossy channels and exponential holding times.