Dynamic Recomputation Cannot Extend the Optimality-Range of Priority Indices

Sequencing rules that rely on priority indices are particularly attractive because they are simple to calculate and easy to implement. It has been established that there are exactly two classes of delay cost functions for which policies that are determined by time-invariant priority indices are capable of producing optimal sequences: linear delay costs and discounted linear delay costs. We consider index-based policies that allow dynamic recalculation of priority indices and show that this class does not enlarge the set of delay cost functions for which index-based rules can produce optimal policies. Our analysis relies on the argument that index-based rules must induce a transitive ranking of the tasks. We show that the classes of linear and discounted linear functions are the only ones that can be associated with such rankings.