Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach |
| |
Authors: | José Niño-Mora |
| |
Institution: | (1) Department of Economics and Business, Universitat Pompeu Fabra, 08005 Barcelona, Spain. From April 2003: Departamento de Estadí′stica y Econometrí′a, Universidad Carlos III de Madrid, 28903 Getafe, Spain. e-mail: jnimora@alum.mit.edu, ES |
| |
Abstract: | 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?o-Mora (2001): Restless bandits, partial conservation laws and indexability.
Adv. Appl. Probab. 33, 76–98], where PCLs were shown to imply the optimality of index policies with a postulated structure in stochastic scheduling problems, under admissible linear objectives, and they were deployed to obtain simple sufficient conditions for the existence of Whittle's (1988) RB index (indexability), along with an adaptive-greedy index algorithm. The new contributions include: (i) we develop the polyhedral foundation
of the PCL framework, based on the structural and algorithmic properties of a new polytope associated with an accessible set system -extended polymatroid}); (ii) we present new dynamic allocation 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 new adaptive-greedy index algorithm; (iv) we interpret PCL-indexability as a form of the classic economics law of
diminishing marginal returns, and characterize the index as an optimal marginal cost rate; we further solve a related optimal constrained control problem; (v) we carry out a PCL-indexability analysis of the motivating admission control model, under time-discounted
and long-run average criteria; this 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.
Received: April 2000 / Accepted: October 2002 Published online: December 9, 2002
RID="★"
ID="★" Work partly supported by the Spanish Ministry of Science and Technology (grant BEC2000-1027), NATO (Collaborative
Linkage Grant PST.CLG.976568), and the Joint Spanish-US (Fulbright) Commission for Scientific and Technical Exchange (project
2000-20132)
Key words. Markov decision process – restless bandits – polyhedral combinatorics – extended polymatroid – adaptive-greedy algorithm
– dynamic allocation index – stochastic scheduling – threshold policy – index policy – Gittins index – Klimov index – Whittle
index – control of queues – admission control – routing – make-to-stock – multiclass queue – finite buffers – conservation
laws – achievable performance
Mathematics Subject Classification (1991): (AMS 2000 Subject Classification): 90B36, 90B22, 90C40, 90C57, 90C08 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|