Deadline Scheduling as Restless Bandits

DOI10.1109/TAC.2018.2807924MaRDI QIDQ4682287zbMATH OpenOpenAlexFDO

Authors Zhe Yu, Yunjian Xu, Lang Tong

Publication date 18 September 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.00399

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36) Markov and semi-Markov decision processes (90C40)

Abstract: The problem of stochastic deadline scheduling is considered. A constrained Markov decision process model is introduced in which jobs arrive randomly at a service center with stochastic job sizes, rewards, and completion deadlines. The service provider faces random processing costs, convex non-completion penalties, and a capacity constraint that limits the simultaneous processing of jobs. Formulated as a restless multi-armed bandit problem, the stochastic deadline scheduling problem is shown to be indexable. A closed-form expression of the Whittle's index is obtained for the case when the processing costs are constant. An upper bound on the gap-to-optimality for the Whittle's index policy is obtained, and it is shown that the bound converges to zero as the job arrival rate and the number of available processors increase simultaneously to infinity.

Cited in

(6)

• Scheduling with deadlines and loss functions
• Opportunistic Scheduling as Restless Bandits
• Conditions for indexability of restless bandits and an algorithm to compute Whittle index
• Minimizing the mean slowdown in the M/G/1 queue
• Optimal differentiated threshold characterization for multi-task stochastic deadline scheduling with queuing
• Scalable Whittle index policy for real-time storage allocation in railway container yard

This page was built for publication: Deadline Scheduling as Restless Bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682287)