Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Scheduling a Multiclass Make-to-Order/-Stock Queue

摘要

We address the dynamic scheduling problem for a multi-product facility, where some products are made-to-order (MTO) and others are MTSB (made-to-stock with backorders), modeled as a multiclass MTO/MTSB M/G/1 queue with general convex backorder and stock holding costs. Our goal is twofold: to design a well-grounded and tractable policy coming close to minimizing the long-run average cost rate per unit time; and to give a tractable lower bound on the minimum achievable cost. Our approach is based on formulating the problem as a restless bandit problem (RBP), which concerns the optimal dynamic scheduling of binary-action (engage/rest) stochastic projects (products in our case), developing a new dynamic index policy for it (motivated by the nonexistence of Whittle's (1988) RBP index in our model), and deriving the new index. We further develop a new lower bound on achievable cost, based on a problem relaxation. Our policy is grounded on fundamental economic principles, as our new index measures the marginal productivity rate of work for each project, which is well defined under diminishing returns (to effort). We give conditions for the index's existence (PCL-indexability), based on the framework of partial conservation laws (PCL), introduced by the author. We show that the MTO and MTSB queues are PCL-indexable, and obtain closed formulae for simple (e.g. linear and quadratic) cost rates.