Improving Upon the Generalized cm Rule: A Whittle Approach

• 成果类型: Article; Early Access
• 署名作者: Li, Zhouzi; Gurushankar, Keerthana; Harchol-Balter, Mor; Scheller-Wolf, Alan
• 署名单位: Carnegie Mellon University; Carnegie Mellon University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2025.1987
• 发表日期: 2026-05-19
• 关键词: generalized cm rule; dynamic scheduling; holding cost minimization; Whittle index; restless multiarmed bandit index policy; convex delay-based holding cost; convex delay costs; scheduling flexible servers; WAITING TIME DISTRIBUTIONS; allocation; optimality; service

摘要

Scheduling a stream of jobs whose holding cost changes over time is a classic and practical problem. Specifically, each job is associated with a holding cost (penalty), and a job's instantaneous holding cost is some nondecreasing function of its class and current age (the time it has spent in the system since its arrival). The goal is to schedule the jobs to minimize the time-average total holding cost across all jobs. The seminal paper on this problem, by Van Mieghem in 1995, introduced the generalized c-mu rule for scheduling jobs. Since then, this problem has attracted significant interest but remains challenging because of the absence of a finite-dimensional state space formulation. Consequently, subsequent works focus on more tractable versions of this problem. This paper returns to the original problem for a k-class M/M/1 system. We derive a heuristic that empirically improves upon the generalized c-mu rule and all existing heuristics. Our key idea is to first translate the holding cost minimization problem to a novel restless multiarmed bandit (R-MAB) problem with a finite number of arms, in which each arm's state corresponds to the age of the oldest job in one class. Based on our R-MAB, we next derive a novel Whittle index policy, which is both elegant and intuitive.