When to Switch? Index Policies for Resource Scheduling in Emergency Response. Issue 2 (13th October 2019) - Li, Dong; Ding, Li; Connor, Stephen
Abstract : 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.