DYNAMIC RECOMPUTATION CANNOT EXTEND THE OPTIMALITY-RANGE OF PRIORITY INDEXES
成果类型：
Article
署名作者：
ROTHBLUM, UG; ROTHKOPF, MH
署名单位：
Rutgers University System; Rutgers University New Brunswick
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.4.669
发表日期：
1994
页码：
669-676
关键词：
摘要：
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.