Optimal myopic policies and index policies for stochastic scheduling problems

Stochastic scheduling problems are considered by using discounted dynamic programming. Both maximizing pure rewards and minimizing linear holding costs are treated in one common Markov decision problem. A sufficient condition for the optimality of the myopic policy for finite and infinite horizon is given. For the infinite horizon case the paper shows the optimality of an index policy and gives a sufficient condition for the index policy to be myopic. Moreover, the relation between the two sufficient conditions is discussed.