TY - JOUR

T1 - When to switch? Index policies for resource scheduling in emergency response

AU - Li, Dong

AU - Ding, Li

AU - Connor, Stephen

PY - 2020/2/28

Y1 - 2020/2/28

N2 - This study considers the scheduling of limited resources to a large number of jobs (e.g., medical treatment) with uncertain lifetimes and service times, in the aftermath of a mass casualty incident. Jobs are subject to triage at time zero, and placed into a number of classes. Our goal is to maximize the expected number of job completions. We propose an effective yet simple index policy based on Whittle’s restless bandits approach. The problem concerned features a finite and uncertain time horizon that is dependent upon the service policy, which also determines the decision epochs. Moreover, the number of job classes still competing for service diminishes over time. To the best of our knowledge, this is the first application of Whittle’s index policies to such problems. Two versions of Lagrangian relaxation are proposed in order to decompose the problem. The first is a direct extension of the standard Whittle’s restless bandits approach, while in the second the total number of job classes still competing for service is taken into account; the latter is shown to generalize the former. We prove the indexability of all job classes in the Markovian case, and develop closed-form indices. Extensive numerical experiments show that the second proposal outperforms the first one (that fails to capture the dynamics in the number of surviving job classes, or bandits) and produces more robust and consistent results as compared to alternative heuristics suggested from the literature, even in non-Markovian settings.

AB - This study considers the scheduling of limited resources to a large number of jobs (e.g., medical treatment) with uncertain lifetimes and service times, in the aftermath of a mass casualty incident. Jobs are subject to triage at time zero, and placed into a number of classes. Our goal is to maximize the expected number of job completions. We propose an effective yet simple index policy based on Whittle’s restless bandits approach. The problem concerned features a finite and uncertain time horizon that is dependent upon the service policy, which also determines the decision epochs. Moreover, the number of job classes still competing for service diminishes over time. To the best of our knowledge, this is the first application of Whittle’s index policies to such problems. Two versions of Lagrangian relaxation are proposed in order to decompose the problem. The first is a direct extension of the standard Whittle’s restless bandits approach, while in the second the total number of job classes still competing for service is taken into account; the latter is shown to generalize the former. We prove the indexability of all job classes in the Markovian case, and develop closed-form indices. Extensive numerical experiments show that the second proposal outperforms the first one (that fails to capture the dynamics in the number of surviving job classes, or bandits) and produces more robust and consistent results as compared to alternative heuristics suggested from the literature, even in non-Markovian settings.

U2 - 10.1111/poms.13105

DO - 10.1111/poms.13105

M3 - Journal article

VL - 29

SP - 241

EP - 262

JO - Production and Operations Management

JF - Production and Operations Management

SN - 1059-1478

IS - 2

ER -