| Abstract: | In scheduling medical residents, the objective is often to maximize resident satisfaction across the space of feasible schedules, relative to the many hard constraints that ensure appropriate patient coverage, adequate training opportunities, etc. A common metric of resident satisfaction is the number of time‐off requests that are granted. Simply maximizing this total, however, may lead to undesirable schedules since some requests have higher priority than others. For example, it might be better to grant one resident's request for a family member's wedding in place of two residents’ requests to attend a rugby game. Another approach is to assign a weight to each request and maximize the total weight of granted requests, but determining weights that accurately represent residents’ and schedulers’ preferences can be quite challenging. Instead, we propose to identify the exhaustive collection of maximally feasible and minimally infeasible sets of requests which can then be used by schedulers to select their preferred solution. Specifically, we have developed two algorithms, which we call Sequential Request Selection Via Cuts (Sequential RSVC) and Simultaneous Request Selection Via Cuts (Simultaneous RSVC), to identify these sets by solving two sequences of optimization problems. We present these algorithms along with computational results based on a real‐world problem of scheduling residents at the University of Michigan C.S. Mott Pediatric Emergency Department. Although we focus our exposition on the problem of resident scheduling, our approach is applicable to a broad class of problems with soft constraints. |
