Restless bandit marginal productivity indices, diminishing returns, and optimal control of make-to-order/make-to-stock M/G/1 queues

• 成果类型: Article
• 署名作者: Niño-Mora, J
• 署名单位: Universidad Carlos III de Madrid
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1050.0165
• 发表日期: 2006
• 页码: 50-84
• 关键词: dynamic allocation indexes; polyhedral approach; conservation-laws; optimal policies; queuing system; optimization; performance; average; server

摘要

This paper presents a framework grounded on convex optimization and economics ideas to solve by index policies problems of optimal dynamic allocation of effort to a discrete-state (finite or countable) binary-action (work/rest) semi-Markov restless bandit project, elucidating issues raised by previous work. Its contributions include: (i) the concept of a restless bandit's marginal productivity index (MPI), characterizing optimal policies relative to general cost and work measures; (ii) the characterization of indexable restless bandits as those satisfying diminishing marginal returns to work, consistently with a nested family of threshold policies; (iii) sufficient indexability conditions via partial conservation laws (PCLs); (iv) the characterization of the MPI as an optimal marginal productivity rate relative to feasible active-state sets; (v) application to semi-Markov bandits under several criteria, including a new mixed average-bias criterion; and (vi) PCL-indexability analyses and MPIs for optimal service control of make-to-order/make-to-stock queues with convex holding costs, under discounted and average-bias criteria.