Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach

Abstract

This paper develops a polyhedral approach to the design, analysis, and computation of dynamic allocation indices for scheduling binary-action (engage/rest) Markovian stochastic projects which can change state when rested (restless bandits (RBs)), based on partial conservation laws (PCLs). This extends previous work by the author [J. Niño-Mora. Restless bandits, partial conservation laws and indexability. Adv. Appl. Probab., vol. 33, 76-98, 2001], where PCLs were shown to imply optimality of index policies with a postulated structure under admissible linear objectives, and they were deployed to obtain sufficient conditions for the existence of Whittle's index and an adaptive-greedy index algorithm. The contributions include: (i) we develop the polyhedral foundation of the PCL framework, based on structural and algorithmic properties of a polytope associated with an accessible set system ($\mathcal{F}$-extended polymatroid); (ii) we present new indices for RBs, motivated by an admission control model, which extend Whittle's and have a significantly increased scope; (iii) we deploy PCLs to obtain both sufficient conditions for the existence of the new indices (PCL-indexability) and a reformulated adaptive-greedy index algorithm; (iv) we interpret PCL-indexability in terms of the economic law of diminishing marginal returns and characterize the index as an optimal marginal cost rate; (v) we carry out a PCL-indexability analysis of the motivating admission control model, which gives, under mild conditions, a new index characterization of optimal threshold policies; and (vi) we apply the latter to present new heuristic index policies for two hard queueing control problems: admission control and routing to parallel queues; and scheduling a multiclass make-to-stock queue with lost sales, both under state-dependent holding cost rates and birth-death dynamics.

arXiv comment3 figures

Cited by in corpus (17)

• Dynamic priority allocation via restless bandit marginal productivity indices
• Computing a classic index for finite-horizon bandits
• A $(2/3)n^3$ fast-pivoting algorithm for the Gittins index and optimal stopping of a Markov chain
• A faster index algorithm and a computational study for bandits with switching costs
• Resource allocation and routing in parallel multi-server queues with abandonments for cloud profit maximization
• Markovian restless bandits and index policies: A review
• A Verification Theorem for Threshold-Indexability of Real-State Discounted Restless Bandits
• Admission and routing of soft real-time jobs to multiclusters: Design and comparison of index policies
• Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies
• A fast-pivoting algorithm for Whittle's restless bandit index
• Multi-gear bandits, partial conservation laws, and indexability
• Joint Opportunistic Scheduling in Multi-Cellular Systems
• A unifying computations of Whittle's Index for Markovian bandits
• Age of information cost minimization with no buffers, random arrivals and unreliable channels: A PCL-indexability analysis
• Solving Poisson's equation for birth-death chains: Structure, instability, and accurate approximation
• Characterization of the Gittins index for sequential multistage jobs
• Energy-Efficient Job-Assignment Policy with Asymptotically Guaranteed Performance Deviation