Asymptotically Optimal Lagrangian Priority Policy for Deadline Scheduling With Processing Rate Limits

• 成果类型: Article
• 署名作者: Hao, Liangliang; Xu, Yunjian; Tong, Lang
• 署名单位: Chinese University of Hong Kong; Cornell University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3049340
• 发表日期: 2022
• 页码: 236-250
• 关键词: Program processors; Processor scheduling; indexes; dynamic scheduling; PROCESS CONTROL; Electric vehicle charging; Time-varying systems; Deadline scheduling; dynamic programming; electric vehicle (EV) charging; index policy; restless multiarmed bandit (RMAB)

摘要

We study the deadline scheduling problem for multiple deferrable jobs that arrive in a random manner and are to be processed before individual deadlines. The processing of the jobs is subject to a time-varying limit on the total processing rate at each stage. We formulate the scheduling problem as a restless multiarmed bandit problem. Relaxing the scheduling problem into multiple independent single-arm scheduling problems, we define the Lagrangian priority value as the greatest tax under which it is optimal to activate the arm. We propose a Lagrangian priority policy that processes jobs in the order of their Lagrangian priority values, and establish its asymptotic optimality as the system scales. Numerical results show that the proposed Lagrangian priority policy achieves 22%-49% higher average reward than the classical Whittle index policy (that does not take into account the processing rate limits).