This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Niño-Mora, J. Search for Related Content

Restless Bandit Marginal Productivity Indices, Diminishing Returns, and Optimal Control of Make-to-Order/Make-to-Stock M/G/1 Queues

Department of Statistics, Universidad Carlos III de Madrid, C/Madrid 126, E-28903 Getafe (Madrid), Spain
jnimora{at}alum.mit.edu, http://alum.mit.edu/www/jnimora

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.

Key Words: restless bandits; stochastic scheduling; index policies; indexability; control by price; semi-Markov decision processes; dynamic resource allocation; diminishing returns; marginal productivity; efficient frontier; convex optimization; bias; mixed criteria; make to order; make to stock; control of queues; production-inventory control; partial conservation laws; achievable performance
History: Received: February 16, 2004; revision received: October 27, 2004;

This article has been cited by other articles:

				J. Nino-Mora A Faster Index Algorithm and a Computational Study for Bandits with Switching Costs INFORMS Journal on Computing, January 1, 2008; 20(2): 255 - 269. [Abstract] [PDF]

				J. Nino-Mora A (2/3)n3 Fast-Pivoting Algorithm for the Gittins Index and Optimal Stopping of a Markov Chain INFORMS Journal on Computing, January 1, 2007; 19(4): 596 - 606. [Abstract] [PDF]