Rights statement: © ACM, 2011.This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in VALUETOOLS '11 Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools http://doi.acm.org/10.4108/icst.valuetools.2011.245797
Accepted author manuscript, 277 KB, PDF document
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Optimal index rules for single resource allocation to stochastic dynamic competitors
AU - Jacko, Peter
N1 - © ACM, 2011.This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in VALUETOOLS '11 Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools http://doi.acm.org/10.4108/icst.valuetools.2011.245797
PY - 2011
Y1 - 2011
N2 - In this paper we present a generic Markov decision process model of optimal single resource allocation to a collection of stochastic dynamic competitors. The main goal is to identify sufficient conditions under which this problem is optimally solved by an index rule. The main focus is on the frozen-if-not-allocated assumption, which is notoriously found in problems including the multi-armed bandit problem, tax problem, Klimov network, job sequencing, object search and detection. The problem is approached by a Lagrangian relaxation and decomposed into a collection of normalized parametric single-competitor subproblems, which are then optimally solved by the well-known Gittins index. We show that the problem is equivalent to solving a time sequence of its Lagrangian relaxations. We further show that our approach gives insights on sufficient conditions for optimality of index rules in restless problems (in which the frozen-if-not-allocated assumption is dropped) with single resource; this paper is the first to prove such conditions.
AB - In this paper we present a generic Markov decision process model of optimal single resource allocation to a collection of stochastic dynamic competitors. The main goal is to identify sufficient conditions under which this problem is optimally solved by an index rule. The main focus is on the frozen-if-not-allocated assumption, which is notoriously found in problems including the multi-armed bandit problem, tax problem, Klimov network, job sequencing, object search and detection. The problem is approached by a Lagrangian relaxation and decomposed into a collection of normalized parametric single-competitor subproblems, which are then optimally solved by the well-known Gittins index. We show that the problem is equivalent to solving a time sequence of its Lagrangian relaxations. We further show that our approach gives insights on sufficient conditions for optimality of index rules in restless problems (in which the frozen-if-not-allocated assumption is dropped) with single resource; this paper is the first to prove such conditions.
U2 - 10.4108/icst.valuetools.2011.245797
DO - 10.4108/icst.valuetools.2011.245797
M3 - Conference contribution/Paper
SN - 978193968091
SP - 425
EP - 433
BT - VALUETOOLS '11 Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools
PB - ACM
CY - New York
T2 - 5th International ICST Conference on Performance Evaluation Methodologies and Tools
Y2 - 16 May 2011 through 20 May 2011
ER -