Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On the dynamic allocation of assets subject to failure
AU - Ford, Stephen
AU - Atkinson, Michael P.
AU - Glazebrook, Kevin
AU - Jacko, Peter
PY - 2020/7/1
Y1 - 2020/7/1
N2 - Motivated by situations arising in surveillance, search and monitoring, in this paper we study dynamic allocation of assets which tend to fail, requiring replenishment before being once again available for operation on one of the available tasks. We cast the problem as a closed-system continuous-time Markov decision process with impulsive controls, maximising the long-term time-average sum of per-task reward rates. We then formulate an open-system continuous-time approximative model, whose Lagrangian relaxation yields a decomposition (innovatively extending the restless bandits approach), from which we derive the corresponding Whittle index. We propose two ways of adapting the Whittle index derived from the open-system model to the original closed-system model, a naïve one and a cleverly modified one. We carry out extensive numerical performance evaluation of the original closed-system model, which indicates that the cleverly modified Whittle index rule is nearly optimal, being within 1.6% (0.4%, 0.0%) of the optimal reward rate 75% (50%, 25%) of the time, and significantly superior to uniformly random allocation which is within 22.0% (16.2%, 10.7%) of the optimal reward rate. Our numerical results also suggest that the Whittle index must be cleverly modified when adapting it from the open-system, as the naïve Whittle index rule is not superior to a myopic greedy policy.
AB - Motivated by situations arising in surveillance, search and monitoring, in this paper we study dynamic allocation of assets which tend to fail, requiring replenishment before being once again available for operation on one of the available tasks. We cast the problem as a closed-system continuous-time Markov decision process with impulsive controls, maximising the long-term time-average sum of per-task reward rates. We then formulate an open-system continuous-time approximative model, whose Lagrangian relaxation yields a decomposition (innovatively extending the restless bandits approach), from which we derive the corresponding Whittle index. We propose two ways of adapting the Whittle index derived from the open-system model to the original closed-system model, a naïve one and a cleverly modified one. We carry out extensive numerical performance evaluation of the original closed-system model, which indicates that the cleverly modified Whittle index rule is nearly optimal, being within 1.6% (0.4%, 0.0%) of the optimal reward rate 75% (50%, 25%) of the time, and significantly superior to uniformly random allocation which is within 22.0% (16.2%, 10.7%) of the optimal reward rate. Our numerical results also suggest that the Whittle index must be cleverly modified when adapting it from the open-system, as the naïve Whittle index rule is not superior to a myopic greedy policy.
KW - Control
KW - Dynamic programming
KW - Heuristics
KW - Queueing
U2 - 10.1016/j.ejor.2019.12.018
DO - 10.1016/j.ejor.2019.12.018
M3 - Journal article
VL - 284
SP - 227
EP - 239
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -