Optimality of index policies for stochastic scheduling with switching penalties (Q4031668)

This paper deals with a system of \(N\) queues (nodes) and a single server characterized by the corresponding service distribution and holding cost, and addresses the questions of switching cost and switching delay arising in the scheduling of jobs initially present in the system. Questions of this type are known in the literature as optimal stochastic scheduling policies and attempt to describe issues of resource allocations encountered in manufacturing, computer and communication networks. Under the assumption the length of the service period for all jobs are mutually independent random variables, the authors formulate in Section 2 a switching cost and a switching delay problem with discounts. In Section 3, one proves that only exhaustive policies can be optimal, i.e. when the server switches to other queue only after hanving served all the customers in the queue. In last section, one reduces the problem to one amenable to Gittins-index techniques under the assumption of equal switching costs and equally distributed delays for all queues. A discussion of the optimal index rule closes the paper.