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

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~no-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 (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.