A suboptimality bound for permutation policies in single machine stochastic scheduling

A general class of single machine stochastic scheduling problems incorporating precedence constraints is modelled as a family of competing Markov decision processes. A bound on the optimal return yields a suboptimality bound for permutation policies. This in turn leads to a generalised ‘used better than new’ principle as a (highly intuitive) sufficient condition for the optimality of a permutation policy in the class of all (preemptive) policies.