Optimality of index policies for stochastic scheduling with switching penalties

The authors investigate the impact of switching penalties on the nature of optimal scheduling policies for systems of parallel queues without arrivals. They study two types of swtiching penalties incurred when switching between queues: lump sum costs and time delays. Under the assumption that the service periods of jobs in a given queue possess the same distribution, the authors derive an index rule that defines an optimal policy. For switching penalites that depend on the particular nodes involved in a switch, they show that although an index rule is not optimal in general, there is an exhaustive service policy that is optimal.