License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05031.13
URN: urn:nbn:de:0030-drops-644
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/64/
Go to the corresponding Portal

Niño-Mora, José

Marginal productivity index policies for scheduling restless bandits with switching penalties

pdf-format:
05031.NinoMoraJose.ExtAbstract.64.pdf (0.2 MB)

Abstract

We address the problem of designing a tractable, well-grounded policy for the dynamic allocation of effort to a collection of restless bandit projects, i.e. binary-action (active/passive) Markov decision processes, in which sequence-independent switching penalties (costs or delays) are incurred when switching from one project to another. We deploy the framework of partial conservation laws, introduced by Ni�±o-Mora (2001, 2002), to establish the existence of and calculate a marginal productivity index (MPI), under certain conditions. The MPI, which extends earlier indices proposed by Gittins (1979) and Whittle (1988), yields a corresponding MPI policy, which prescribes to dynamically engage the project with larger index.

BibTeX - Entry

@InProceedings{ninomora:DagSemProc.05031.13,
  author =	{Ni\~{n}o-Mora, Jos\'{e}},
  title =	{{Marginal productivity index policies for scheduling restless bandits with switching penalties}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/64},
  URN =		{urn:nbn:de:0030-drops-644},
  doi =		{10.4230/DagSemProc.05031.13},
  annote =	{Keywords: stochastic scheduling , restless bandits , index policies , switching penalties}
}

Keywords: stochastic scheduling , restless bandits , index policies , switching penalties
Collection: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI