RESTLESS BANDIT MARGINAL PRODUCTIVITY INDICES II: MULTIPROJECT CASE AND SCHEDULING A MULTICLASS MAKE-TO-ORDER/-STOCK M/G/1 QUEUE

This paper develops a framework based on convex optimization and economic ideas to formulate and solve approximately a rich class of dynamic and stochastic resource allocation problems, fitting in a generic discrete-state multi-project restless bandit problem (RBP). It draws on the single-project framework in the author´s companion paper “Restless bandit marginal productivity indices I: Single-project case and optimal control of a make-to-stock M/G/1 queue”, based on characterization of a project´s marginal productivity index (MPI). Our framework significantly expands the scope of Whittle (1988)´s seminal approach to the RBP. Contributions include: (i) Formulation of a generic multi-project RBP, and algorithmic solution via single-project MPIs of a relaxed problem, giving a lower bound on optimal cost performance; (ii) a heuristic MPI-based hedging point and index policy; (iii) application of the MPI policy and bound to the problem of dynamic scheduling for a multiclass combined MTO/MTS M/G/1 queue with convex backorder and stock holding cost rates, under the LRA criterion; and (iv) results of a computational study on the MPI bound and policy, showing the latter´s near-optimality across the cases investigated.