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 - A conservative index heuristic for routing problems with multiple heterogeneous service facilities
AU - Shone, R.
AU - Knight, V.A.
AU - Harper, P.R.
PY - 2020/12/1
Y1 - 2020/12/1
N2 - We consider a queueing system with N heterogeneous service facilities, in which admission and routing decisions are made when customers arrive and the objective is to maximize long-run average net rewards. For this type of problem, it is well-known that structural properties of optimal policies are difficult to prove in general and dynamic programming methods are computationally infeasible unless N is small. In the absence of an optimal policy to refer to, the Whittle index heuristic (originating from the literature on multi-armed bandit problems) is one approach which might be used for decision-making. After establishing the required indexability property, we show that the Whittle heuristic possesses certain structural properties which do not extend to optimal policies, except in some special cases. We also present results from numerical experiments which demonstrate that, in addition to being consistently strong over all parameter sets, the Whittle heuristic tends to be more robust than other heuristics with respect to the number of service facilities and the amount of heterogeneity between the facilities.
AB - We consider a queueing system with N heterogeneous service facilities, in which admission and routing decisions are made when customers arrive and the objective is to maximize long-run average net rewards. For this type of problem, it is well-known that structural properties of optimal policies are difficult to prove in general and dynamic programming methods are computationally infeasible unless N is small. In the absence of an optimal policy to refer to, the Whittle index heuristic (originating from the literature on multi-armed bandit problems) is one approach which might be used for decision-making. After establishing the required indexability property, we show that the Whittle heuristic possesses certain structural properties which do not extend to optimal policies, except in some special cases. We also present results from numerical experiments which demonstrate that, in addition to being consistently strong over all parameter sets, the Whittle heuristic tends to be more robust than other heuristics with respect to the number of service facilities and the amount of heterogeneity between the facilities.
KW - Dynamic programming
KW - Queueing systems
KW - Whittle index heuristic
KW - Decision making
KW - Structural optimization
KW - Structural properties
KW - Dynamic programming methods
KW - Heterogeneous services
KW - Multi-armed bandit problem
KW - Number of services
KW - Numerical experiments
KW - Optimal policies
KW - Routing decisions
KW - Routing problems
U2 - 10.1007/s00186-020-00722-w
DO - 10.1007/s00186-020-00722-w
M3 - Journal article
VL - 92
SP - 511
EP - 543
JO - Mathematical Methods of Operational Research
JF - Mathematical Methods of Operational Research
SN - 1432-2994
IS - 3
ER -