Better Scheduling When the Cost of Delay Grows over Time Imagine a stream of jobs, in which each job costs us some money (a holding cost) for every hour that it is not complete. Furthermore, the holding cost of each job can increase over time and possibly even jump up at deadlines associated with the job. To minimize the rate at which we hemorrhage money, it is common to deploy well-known strategies such as the celebrated generalized c-mu rule, which prioritizes scheduling jobs based on their instantaneous holding cost. However, this approach is limited: it ignores how costs rise in the future; for example, a job with a deadline might be ignored until after the deadline is missed. Li, Gurushankar, Harchol-Balter, and Scheller-Wolf tackle this time-varying holding cost problem by translating it into a restless multiarmed bandit, which they use to derive a Whittle index. This leads to a new priority rule that accounts for how both holding costs and workloads evolve in the future. Their rule is simple to implement, yet it is remarkably robust, consistently outperforming all known heuristics across a wide range of settings.
Li et al. (Tue,) studied this question.