Improving Upon the Generalized c μ Rule: A Whittle Approach
- 19 May 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (5) , 2577-2591
Abstract
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.Keywords
This publication has 22 references indexed in Scilit:
- Dynamic scheduling with convex delay costs revisitedQueueing Systems, 2025
- Whittle index approach to the multi-class queueing systems with convex holding costs and IHR service timesMathematical Methods of Operations Research, 2024
- Dynamic Control of Birth-and-Death Restless Bandits: Application to Resource-Allocation ProblemsIEEE/ACM Transactions on Networking, 2016
- Waiting Time Distributions in the Preemptive Accumulating Priority QueueMethodology and Computing in Applied Probability, 2015
- Waiting time distributions in the accumulating priority queueQueueing Systems, 2013
- Performance Modeling and Design of Computer Systems2013
- The single-server scheduling problem with convex costsQueueing Systems, 2012
- Index Heuristics for Multiclass M/G/1 Systems with Nonpreemptive Service and Convex Holding CostsQueueing Systems, 2003
- Whittle's index policy for a multi-class queueing system with convex holding costsMathematical Methods of Operations Research, 2003
- Bandit Processes and Dynamic Allocation IndicesJournal of the Royal Statistical Society Series B: Statistical Methodology, 1979