Essays on indexability of stochastic sheduling and dynamic allocation problems

Ruíz Hernández, Diego

Essays on indexability of stochastic sheduling and dynamic allocation problems

Document Type

Doctoral thesis
Published Version

Author

Ruíz Hernández, Diego

Director

Glazebrook, Kevin

Publication Date

2007-04-13

Citation

Ruíz Hernández, D. Essays on indexability of stochastic sheduling and dynamic allocation problems. Universitat Pompeu Fabra; 2007. handle: http://hdl.handle.net/10803/7347

This citation was generated automatically.

Doctoral program

Programa de doctorat en Economia, Finances i Empresa

Abstract

In this Thesis, we first deploy Gittins index theory to establish the indexability of inter-alia general families of restless bandits that arise in problems of stochastic scheduling with switching penalties and machine maintenance. We also give formulae for the resulting indices. Numerical investigations testify the strong performance of the index heuristics.<br/><br/>The second class of problems concerns two families of Markov decision problems. The spinning plates problem concerns the optimal management of a portfolio of assets whose yields grow with investment but otherwise decline. In the model of asset exploitation called the squad system, the yield from an asset declines when it is utilised but will recover when the asset is at rest. Simply stated conditions are given which guarantee general indexability of the problem together with necessary and sufficient conditions for strict indexability. The index heuristics, which emerge from the analysis, are assessed numerically and found to perform strongly.

Keywords

Machine Maintenance, Switching Penalties, Indexability, Gittins Indices, Restless Bandits, Multi-armed Bandit Problems, Dynamic Programming, Stochastic Scheduling, Dynamic Allocation, Markov Decision Problems