operation research homework

This article was downloaded by: [132.174.254.97] On: 25 February 2017, At: 11:26 Publisher: Institute for Operations Research and the Management Sciences (INFORMS) INFORMS is located in Maryland, USA Interfaces Publication details, including instructions for authors and subscription information:

http://pubsonline.informs.org Scheduling Medical Residents at Boston University School of Medicine Amy Cohn, Sarah Root, Carisa Kymissis, Justin Esses, Niesha Westmoreland, To cite this article:

Amy Cohn, Sarah Root, Carisa Kymissis, Justin Esses, Niesha Westmoreland, (2009) Scheduling Medical Residents at Boston University School of Medicine. Interfaces 39(3):186-195. http://dx.doi.org/10.1287/inte.1080.0369 Full terms and conditions of use: http://pubsonline.informs.org/page/terms-and-conditions This article may be used only for the purposes of research, teaching, and/or private study. Commercial use or systematic downloading (by robots or other automatic processes) is prohibited without explicit Publisher approval, unless otherwise noted. For more information, contact [email protected]. The Publisher does not warrant or guarantee the article’s accuracy, completeness, merchantability, fitness for a particular purpose, or non-infringement. Descriptions of, or references to, products or publications, or inclusion of an advertisement in this article, neither constitutes nor implies a guarantee, endorsement, or support of claims made of that product, publication, or service. Copyright © 2009, INFORMS Please scroll down for article—it is on subsequent pages INFORMS is the largest professional society in the world for professionals in the fields of operations research, management science, and analytics.

For more information on INFORMS, its publications, membership, or meetings visit http://www.informs.org Vol. 39, No. 3, May–June 2009, pp. 186–195 issn0092-2102 eissn1526-551X 09 3903 0186 inf orms ® doi10.1287/inte.1080.0369 © 2009 INFORMS Scheduling Medical Residents at Boston University School of Medicine Amy Cohn Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109, [email protected] Sarah Root Department of Industrial Engineering, University of Arkansas, Fayetteville, Arkansas 72703, [email protected] Carisa Kymissis Department of Psychiatry, St. Luke’s Hospital, New York, New York 10025, [email protected] Justin Esses Boston University School of Medicine, Boston, Massachusetts 02118, [email protected] Niesha Westmoreland Monteﬁore Medical Center, Bronx, New York 10467, nwestmor@monteﬁore.org The chief residents in the psychiatry program at Boston University School of Medicine (BUSM) must construct a schedule that simultaneously assigns residents to ﬁve types of call shifts, spanning three different hospitals, over a 365-day planning horizon. We show how user expertise and heuristic approaches alone fail to ﬁnd acceptable solutions to this complex combinatorial problem; likewise, mathematical programming techniques alone are inadequate, largely because they lack a clearly deﬁnable objective function. However, by combining both approaches, we were able to ﬁnd high-quality solutions in a very short time. The resulting schedule, which BUSM uses currently, has yielded substantial beneﬁts; the solution quality has improved, and the effort required to develop the solution has been reduced.

Key words: philosophy of modeling; health care: hospitals; integer programming applications; multiple criteria.

History: This paper was refereed. Published online inArticles in AdvanceFebruary 18, 2009. I n this paper, we discuss our experience in con- structing the annual on-call schedule for medi- cal residents specializing in psychiatry at Boston University School of Medicine (BUSM).

As part of their education, doctors typically spend four years in medical school, followed by at least three to ﬁve years as residents—certiﬁed and practic- ing physicians who are training under the supervision of more senior physicians. At BUSM, the psychia- try residents have daytime responsibilities, such as patient care and seminars. In addition, they are also required to be on call some nights during the aca- demic year (which runs from July 1 to June 30). When on call, the residents must be at the assigned hospital from 5pmuntil 8amthe following morning.

On-call shifts serve two purposes—to provide train- ing to the residents and stafﬁng for the hospitals.

To meet both needs, the chief resident must build aschedule assigning second- and third-year residents (“PGY2s” and “PGY3s” based on their number of “p ost-g raduation y ears” from medical school) to pro- vide coverage at three hospitals. This schedule must ensure that each resident completes the appropriate number of calls at each hospital during the academic year to fulﬁll his or her educational requirements.

It cannot violate rules, such as those designed to ensure adequate rest for the residents. In addition, each hospital must have appropriate stafﬁng to meet patient needs. Finally, each resident has individual preferences and requests—for example, speciﬁc days off to attend a family wedding.

Developing high-quality call schedules is impor- tant. For the chief residents, who take the brunt of the residents’ dissatisfaction with their assignments, the task of constructing the schedule has traditionally been extremely time-consuming and frustrating. For 186Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of MedicineInterfaces 39(3), pp. 186–195, © 2009 INFORMS 187 the individual residents, the quality of the schedule directly affects their quality of life—e.g., the amount of rest they get and their ability to attend family func- tions. The schedule also impacts the residency pro- gram because violations in labor restrictions could lead to loss of accreditation. Finally, and perhaps most importantly, the spacing between residents’ call shifts, and thus the amount of rest (or lack thereof) that they can get in any given time period, directly impacts the quality of patient care.

The task of simultaneously assigning 10 to 20 residents (each with individual scheduling require- ments and requests) to cover three hospitals (which also have unique requirements) over the course of 365 days is a signiﬁcant combinatorial challenge. Any one decision (e.g., assigning a single resident to a sin- gle on-call shift) could have signiﬁcant impact on the rest of the schedule. Traditionally, the chief residents undertook this daunting task with little assistance from decision-support tools. As a result, ﬁnding a schedule that is even feasible relative to the hard con- straints, let alone honors the preferences of the indi- vidual residents, was virtually impossible. Although the practical experience and innate logical capabili- ties of the chief residents helped them to address this challenge, signiﬁcant weaknesses still existed in the resulting schedules, including a failure to fully sat- isfy all restrictions on mandated length-of-time limits between scheduled calls.

Given the many complex, interconnecting decisions in this problem, mathematical programming seems, at ﬁrst glance, to be a logical alternative to the chief resi- dents’ ad hoc scheduling methods. However, there are also signiﬁcant challenges associated with applying mathematical programming techniques to this prob- lem. The most signiﬁcant is the lack of a clear-cut objective function.

The on-call scheduling problem is clearly not just a feasibility problem—a schedule that satisﬁesallvaca- tion requests is certainly better than one that does not satisfyanyvacation requests. However, what if multiple important criteria exist? How should trade- offs be made between different metrics? For example, what is the value of granting a vacation relative to the value of limiting the number of Friday nights that an individual must work? Quantifying such preferences is very difﬁcult, and asking the residents to providenumerical weights for each of several different metrics is unlikely to result in a schedule that actually rep- resents their true preferences. Furthermore, the chief residents have the added challenge of ensuring equity acrossthe set of residents, making sure that one res- ident is not assigned a highly desirable schedule at the expense of another resident being assigned a very poor schedule, while also balancing the needs of the hospitals.

This problem is neither a feasibility problem nor an optimization problem; rather, it is something in between. It is not necessary to ﬁnd the “optimal” solution because it does not exist. Nonetheless, the chief residents have some threshold of what is “good enough.” Therefore, our goal was to ﬁrst ﬁnd a sched- ule that satisﬁed all the hard constraints. Then, by working with the chief residents interactively, we could work to improve the quality of this schedule by providing candidate schedules and identifying weak- nesses. Based on this new knowledge, we could then seek to ﬁnd improvements and repeat the process.

Using a combination of mathematical program- ming, feedback from the chief residents, and iterative improvements to the model, we were able to ﬁnd a high-quality solution, which the hospitals are using today. The sections that follow outline this process. Problem Description At BUSM, PGY2s and PGY3s must be scheduled to cover on-call shifts (from 5pmto 8am) at three hos- pitals during the academic year (July 1 to June 30).

Hospitals A, B, and C are all large academic teaching hospitals. Each has different stafﬁng requirements as we outline below.

• Each PGY2 must spend six consecutive weeks on a rotation at Hospital A. The six-week period is predetermined and serves as an input to our schedul- ing problem. During this period, the resident can only perform on-call shifts at Hospital A; these are sched- uled ofﬂine by Hospital A staff. In other words, each PGY2 has a prespeciﬁed six-week block during which the resident cannot be assigned to any call shifts.

• Each PGY2 and PGY3 has a speciﬁc number of calls (the requirement varies by year) to perform at Hospital B. Hospital B is also staffed by residents from a second residency program. Therefore, there isDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of Medicine 188 Interfaces 39(3), pp. 186–195, © 2009 INFORMS a preset schedule of days on which BUSM residents must provide coverage. On each of these days, one BUSM resident must be assigned as the primary call (this resident is expected to provide coverage except in cases of unplanned events such as illness) and a second resident must be assigned as the backup call, ﬁlling in only if the primary call becomes unavailable.

• The third hospital, Hospital C, is staffed solely by BUSM residents, who again have a ﬁxed number of calls to perform during the year. This hospital does not require backup calls—only one resident must be assigned on each night. However, on some nights, physicians, who are outside of the residency pro- gram and who have requested “moonlighting” oppor- tunities, can provide stafﬁng. These “extra on-calls” (EOCs) are permitted as an alternative to a named resident. The use of EOCs is necessary because the number of call shifts that residents require to fulﬁll their educational requirements is insufﬁcient to fully staff Hospital C each night of the year.

In constructing a feasible schedule to cover these three hospitals, we must observe several hard con- straints.

• Residents cannot be assigned to calls at different hospitals on the same night.

• All hospital coverage requirements must be met.

• A resident cannot be on call more than once in any four-day period.

• A resident cannot be assigned to more than ﬁve calls in any calendar month.

• PGY2s cannot be assigned to be on call on Tuesdays; PGY3s cannot be assigned to be on call on Tuesdays or Wednesdays because these days are reserved for other educational requirements. There- fore, EOCs must provide coverage at Hospital C on Tuesdays; Tuesdays at Hospital B are scheduled in advance to be staffed by the other residency program.

In addition, there are several soft constraints that the scheduling should observe, and preferences of both the individual residents and the chief residents.

• Each resident should complete a prespeciﬁed number of calls (subdivided further into weekday and weekend requirements) at each hospital. In practice, this may not be possible. If so, the same total num- ber of calls should still be scheduled for each resi- dent; however, some of these calls might be swapped between hospitals.• Each resident should be assigned to work a call shift on exactly one holiday during the year. The spe- ciﬁc holidays are typically assigned prior to the sched- ule construction.

• Residents can provide vacation requests prior to the start of the scheduling process.

• Residents prefer that their weekday assignments not be Fridays, and that their weekend assignments be Sundays rather than Saturdays. This is because residents coming off of an overnight call are given reduced work responsibilities during the next day; they lose this beneﬁt if the next day is a Saturday or a Sunday.

• PGY2s spend their days at several different loca- tions. They prefer that, on nights when they are on call, their call location (Hospital A, B, or C) be the hospital closest to their daytime assignment; this min- imizes commuting time and maximizes rest time.

• The chief residents prefer that no one resident receive a signiﬁcantly more desirable schedule than any other resident. The Solution We can capture the basic feasibility problem posed above (i.e., the hard constraints) using a traditional integer programming (IP) formulation. This formula- tion (which the appendix presents) is based on the following sets of binary assignment variables:

•x rd=1 if residentris assigned to the primary call shift at Hospital B on dayd, else zero; •y rd=1 if residentris assigned to backup call at Hospital B on dayd, else zero; •z rd=1 if residentris assigned to Hospital C on dayd, else zero; •e d=1 if an EOC is assigned to Hospital C on dayd, else zero.

Given these variable deﬁnitions, it is straight- forward to model the following rules as linear constraints:

• Residents cannot be assigned to more than one call per night (constraint set (1) in the appendix).

• Hospital C must have an EOC or named resident each night in the planning horizon (constraint set (2) in the appendix).

• Hospital B must have named primary and backup residents each night in the planning horizonDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of MedicineInterfaces 39(3), pp. 186–195, © 2009 INFORMS 189 during which Hospital B is assigned to BUSM (con- straint set (2) in the appendix).

• Residents cannot be assigned to more than one call in any four-day period (constraint set (3) in the appendix).

• Residents cannot be assigned to more than ﬁve calls in any calendar month (constraint set (4) in the appendix).

• PGY2s cannot be assigned to calls on Tuesdays; PGY3s cannot be assigned to calls on Tuesdays or Wednesdays (constraint set (5) in the appendix).

We implemented this model and the supporting infrastructure using C++; we used the Concert Tech- nology libraries of CPLEX for the IP solver. This fea- sibility problem typically solves in less than a minute on a 2.2 GHz laptop computer running Windows XP with 2 GB of RAM.

Once we have formulated the feasibility problem (and know it to be tractable), we can expand the model to compute the value of the different metrics that are import to the residents. Speciﬁcally, we cal- culated the following metrics:

• Number of vacation requests denied (by resi- dent); • Number of EOCs scheduled during the Christmas holiday week; • Number of calls at one hospital substituted in place of the educational requirements at another hospital; • Number of night calls that did not match a resi- dent’s daytime location; • Number of calls per month (by resident); • Number of Friday calls; • Number of Saturday calls.

As we stated above, the key challenge is determining how tousethese metrics—what should the objective be? Within this, there are two secondary questions. First, how should we trade off between different criteria (e.g., vacation days versus preferred days of week) for a given resident? Second, how should we trade off between the residents themselves, in terms of the quality of their respective schedules?

In seeking to answer these questions, let us ﬁrst consider what has been done in the past. This project falls within the area covered by the extensive litera- ture on scheduling health-care personnel. The major- ity of this literature addresses scheduling nurses;nurses are one of the most costly resources in any hospital system. Thenurse scheduling problem(NSP) typically assigns nurses to a series of shifts such that each nurse’s schedule satisﬁes a series of feasibility rules and the schedule ensures adequate stafﬁng lev- els for the hospital. Research summaries can be found in the survey papers of Burke et al. (2004), Cheng et al.

(1997), and Siferd and Benton (1992).

In recent years, NSP has remained an active area of research. The majority of this recent work tends to use metaheuristics such as genetic algorithms (Aickelin and Dowsland 2004), tabu search (Burke et al. 2006), and ant-colony optimization (Gutjahr and Rauner 2007) as solution methods for this prob- lem. Increasingly, hybrid approaches using multiple solution techniques are being used to solve NSP.

For example, Burke et al. (2008) combine heuristic ordering and variable neighborhood search; Burke et al. (2003) develop a hyperheuristic that combines multiple metaheuristics and eliminates the need for instance-dependent tuning of metaheuristic parame- ters; Cipriano et al. (2006) integrate constraint pro- gramming and local search; and Dias et al. (2003) develop a solver that combines tabu search and genetic algorithms. Optimization-based approaches— typically integer programming—have also been used to solve NSP (Azaiez and Al Sharif 2005; Bard and Purnomo 2005a, b, c). Another prominent area of NSP research focuses on algorithms such as the estimation- distribution algorithm (Aickelin and Li 2007), case- based reasoning (Beddoe and Petrovic 2006, Petrovic et al. 2002), and a Bayesian optimization algorithm (Li and Aickelin 2006), all of which imitate and/or incorporate human learning when generating nurse scheduling.

Despite the large and growing body of literature on NSP, there is still a gap between how nurse schedul- ing as described in the literature and as used in practice (Burke et al. 2004). Kellogg and Walczak (2007) state that only 30 percent of published nurse- scheduling models are ever used. To increase the percentages of usage, they suggest that interactions between the nurse scheduler and the nurses being scheduled is critical, particularly in the early stages of model development.

Beaulieu et al. (2000), Carter and Lapierre (2001), Gendreau et al. (2006), Valouxis and Housos (2000),Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of Medicine 190 Interfaces 39(3), pp. 186–195, © 2009 INFORMS and Vassilacopoulos (1985) have done research on scheduling emergency room physicians. Perhaps one of the most closely related papers is that of Sherali et al. (2002), in which resident on-call schedules are created in four to ﬁve-week blocks by exploiting an underlying network structure in the proposed math- ematical program. Another related paper is that of Ozkarahan (1994), which uses goal programming to schedule residents; it focuses on controlling the num- ber of hours and spacing of shifts (therefore, the amount of rest) assigned to the residents. Franz and Miller (1993) consider the problem of scheduling med- ical residents for their daytime rotations by working in close collaboration with the decision maker.

The ﬁnal category of literature relevant to our research is multicriteria optimization. Ehrgott (2005) provides an excellent text on solving optimization problems using multiple important metrics. Ehrgott discusses two common ways to approach multi- criteria combinatorial optimization problems. One approach is the use of a weighted-sum objective func- tion, in which all the metrics are included in the objec- tive function, with corresponding weights to trade off the relative importance of the metrics. This weighted- sum approach is common in NSP (Azaiez and Al Sharif 2005; Bard and Purnomo 2005a, b, c, 2007; Dias et al. 2003). Another approach to multicriteria combi- natorial optimization problems is to ﬁnd thePareto- optimal frontier—the set of all solutions for which improving the value of one metric can only be done at the cost of worsening the value of one or more other metrics. Within the scheduling literature, Landa Silva et al. (2004) provide an excellent reference that focuses on scheduling in a broad context; it also includes a detailed discussion of personnel scheduling, includ- ing NSP.

Although there are many similarities between the problem we faced and the problems commonly dis- cussed in the literature, there are also three key differences. First, the year-long scope (necessary to address the residents’ educational requirements) is signiﬁcantly longer in our case. For example, nurse schedules are often developed in two- or four-week increments. Second, we must consider the stafﬁng needs of three hospitals simultaneously. However, it is the third difference that brings us back to our early questions about how to deﬁne the objective function.Speciﬁcally, when individual preferences are stated as part of the problem deﬁnition, the objective function in the majority of the literature relies on the use of weights to determine the “optimal” trade-offs among different metrics. However, as we have argued, indi- viduals are rarely able to quantify their preferences in a way that can adequately translate to weights that accurately represent their preferences among different solutions. Thus, our research focuses instead on using a multiphased, interactive approach—we provided the chief resident with candidate schedules; they pro- vided feedback that we used to ﬁnd improved solu- tions. The steps of this approach follow.

In the ﬁrst phase, we considered each individual metric (e.g., number of vacation requests granted and maximum number of Friday night calls per resident); we found the optimal solution relative to that met- ric alone by moving the variable used in calculating this metric into the objective function. Typically, this slowed the run time, but not substantially; individual runs still typically took well under ﬁve minutes. Gen- erating these bounds on the individual metrics pro- vided valuable benchmarking information to help us to understand what was feasible within the schedule as a whole. Moreover, it provided helpful information for the chief residents to use in dealing with poten- tial complaints. For example, when a resident com- plained that his or her vacation requests were not all met, the chief residents no longer had to justify their failure to construct a better schedule. Instead, they could rely on mathematical proof to respond that no feasible schedule existed that satisﬁed those requests.

Likewise, the chief residents could argue that no fea- sible schedule existed without at least one resident workingnor more Friday night calls.

In the second phase, the chief residents prioritized the preference criteria. For example, in general, it is more important to residents that their vacation requests be satisﬁed than it is that their number of Sat- urday night calls be limited. We then solved a series of nested optimization problems. We ﬁrst maximized satisfaction relative to the ﬁrst preference criteria. We then ﬁxed this metric as a constraint that must be met (i.e., the satisfaction relative to the ﬁrst metric must continue to meet this level), and maximized satisfac- tion to the second preference criteria, etc. This yielded a feasible schedule that we could present to the chiefDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

In the third phase, we iteratively submitted sched- ules to the chief residents and received their feedback.

This process was invaluable for identifying require- ments and preferences that had not been articulated earlier. For example, because of the large number of vacation requests over the Christmas-New Year ’s week, many of those calls had been assigned to EOCs. The chief residents, in observing this, recalled that in previous years those physicians who typically requested moonlighting opportunities were not avail- able during this holiday week; therefore, ﬁlling these slots was problematic. Thus, we added an additional constraint to the model to restrict the number of EOCs available over that range of dates.

Many of the concerns raised were questions of equity. For example, one resident might be assigned to work many Friday nights, while other residents worked very few. By adding constraints limiting both the maximum and minimum number of Fridays that each resident could work, and then varying these input parameters, we were able to observe the rela- tionship between this preference and other consid- erations within the network. The time required to make any one revision (i.e., to take the chief residents’ feedback, identify modeling and/or data changes designed to address their concerns, implement these changes in the code, and construct a new schedule) took a few hours at most.

Within the ﬁnal, accepted schedule, all vacation requests were granted. Doing so required assign- ing four EOCs during Christmas week; reducing the number of EOCs to three led to sacriﬁcing one request for holiday vacation time; the chief residents opted against this. The number of required calls that had to be “shifted” from one hospital to another (e.g., a resident was supposed to performncalls at one site andmat another, but instead was scheduled forn−1 andm+1, respectively) was also a con- cern. For each resident, there were at most two calls applicable to meeting the educational requirements at Hospital B that had to be satisﬁed by complet- ing a call at Hospital C or vice versa. With regard to day-night location matching, each PGY2 had exactly three calls that did not match between day and night locations in the ﬁnal solution; all others matched.The number of calls per resident per month ranged from three to ﬁve. Although ﬁve is the maximum number of calls permitted per month, it is not ideal; many PGY2s needed multiple months with ﬁve calls because they have less time in which to schedule their educational requirements at Hospitals B and C, given their required time at Hospital A (which occupies a complete and consecutive six-week block). The PGY3s had fewer months with ﬁve calls scheduled, although those who requested large blocks of vacation time needed some months with ﬁve calls to compensate (the residents did not view this as a hardship because they were pleased to have their vacation requests granted). Finally, every resident was assigned to six or seven Friday calls and six or seven Saturdays; there- fore, in total, each was assigned to work either 13 or 14 shifts on these two days of the week.

The ﬁnal schedule became effective a few weeks after its completion (July 1, 2006) and has been in place since then. To quote an e-mail from one of the chief residents, “We are using the schedule in its entirety, exactly as your program generated. There have been surprisingly few requests for call swaps so far. There were no errors that we could detect; the res- idents had no complaints about it. It has been great, and greatly decreased our headaches as Chiefs!” Lessons Learned We summarize here the key lessons that we learned from this project.

(1)Learning and Teaching:It seems obvious to state that the successful use of any OR tool in a prac- tical setting depends on the operations researcher learning as much as possible from the application expert. However, we learned that teaching the appli- cation experts (i.e., the chief residents) about OR, not just learning from them, is critical. By developing an understanding of “how OR works,” the applica- tion experts can communicate their requirements and goals better. As the chief residents began to under- stand how different requirements would make the model more difﬁcult to solve (and thus slow the research process), we gave them control over trading off which aspects of the problem must be included and which could be ignored to ensure a more timely result. They also began to think differently aboutDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of Medicine 192 Interfaces 39(3), pp. 186–195, © 2009 INFORMS decisions and constraints. It was a very satisfying moment when, during a conference call over some last-minute changes, one chief resident said wor- riedly, “We have one resident who has to fulﬁll just a handful of requirements, with speciﬁc dates already determined—can we do that?” and another jumped in to suggest, “Can’t we just treat those as preassigned holidays?” This is exactly how we modeled it.

(2)A Common Language:The challenges that can arise because of differences in terminology are impor- tant. For example, what an operations researcher interprets as a hard constraint (“The solution must have the following characteristic ”) might instead be a strong preference for the end user (“ unless that is not possible, or unless it prevents something else that I care about more.”). As another example, a colleague reports often hearing physicians refer to one solution as being “more optimal” than another. Being aware of these differences in terminology and work- ing to bridge this gap can be essential to a successful application.

(3)It Is Not Always Optimal to Optimize:As math- ematical programmers, we often start with the goal of “seeking an optimal solution to a problem.” The notion that such a solution cannot be found—and that it is does not even exist—is one that we found difﬁcult to accept initially. However, it became clear that trying to ﬁnd an optimal solution was nei- ther possible nor appropriate. The goals of the chief residents were to satisfy all hard constraints (if pos- sible), treat all residents fairly, satisfy preferences whenever possible, and build the schedule without making an excessive time commitment. By developing a mathematical-programming-based tool that could enforce rules and be easily modiﬁed, we were able to determine whether the hard constraints could be sat- isﬁed and, if not, modify them accordingly. For exam- ple, we ﬁrst demonstrated that all residents could not complete the same number of calls at each hospital.

Next, we were able to provide insights on the limits of different metrics. For example, we computed the minimum number of Friday nights that the resident with the highest number of Friday calls would have to work. Finally, as the chief residents identiﬁed what they liked and did not like about the sample sched- ules, we used the strengths of mathematical program- ming to either improve the schedule or to demonstrate that a given metric could not be improved uponwithout making other (more important) metrics worse. Ultimately, we were able to meet the chief res- idents’ goals—a schedule that required minimal time to construct, raised no complaints from the residents, and did not violate the hard constraints. Although the result was not an “optimal” schedule from a theoret- ical standpoint, it is exactly what the chief residents wanted. Conclusions and Future Research In this paper, we outlined an important problem in the scheduling of health-care personnel. Speciﬁcally, we looked at the development of residency call sched- ules. This problem presents signiﬁcant challenges not commonly found in the health-care scheduling litera- ture. First, the problem spans an extended period (a full academic year). Second, it encompasses multiple sites (three hospitals) and multiple staff requirements (residents each have different educational goals to be met), in addition to multiple types of calls (primary, backup, and EOC). Third, the number of metrics of importance to the individual residents is sizeable and the chief residents, who are responsible for building the schedule, have the added burden of constructing a schedule that is deemed “equitable” to all residents.

We solved this problem by formulating a mixed- integer feasibility problem that captures all the sys- tem’s hard constraints. We also included constraints within this model to compute the value of each of the different metrics. Then, in an iterative exchange with the chief residents, we imposed varying limits on these metrics to develop a schedule that trades off between these metrics at a level that is acceptable to them.

This approach provided substantial beneﬁts both to the chief residents and the residency program. It reduced the effort required to produce the sched- ule substantially and improved the quality of the schedule from the perspective of the residents’ per- sonal preferences. Perhaps most importantly, how- ever, it provided complete compliance with all hard constraints (this had not been the case in the past).

These rules focus on ensuring suitable periods of rest for the residents, a factor that has signiﬁcant impact on patient care quality.

Although the chief residents were extremely satis- ﬁed with the outcome of this project, opportunities forDownloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

Cohn et al.:Scheduling Medical Residents at Boston University School of MedicineInterfaces 39(3), pp. 186–195, © 2009 INFORMS 193 improvement remain. The most important of these is increasing the automation of the scheduling process.

The process of building the 2006–2007 schedule, as we outlined in this paper, required extensive interaction between the OR analysts and the chief residents—to deﬁne the problem, outline the hard constraints, and identify important metrics. Then, after the model was developed, implemented, and tested, there were sev- eral rounds of discussion and evaluation. The OR analysts would submit a schedule, the chiefs would evaluate it and identify ﬂaws, and the OR analysts would make changes to the model and construct a new schedule; these steps would then be repeated.

Although this method was successful in helping us to develop an understanding of the problem and con- struct the associated model and software, it is not practical for ongoing use.

To develop the 2007–2008 schedule, we worked together again, but interactively and with signiﬁ- cantly less effort. In preparation for the new schedul- ing process, we streamlined the implementation of the model, making it more general and thus better equipped to incorporate changes in system rules and requirements quickly. We also streamlined the way in which we captured changes in boundaries on the metrics in the code (“Make the maximum number of vacations denied two instead of three”). Nonetheless, the chiefs were still largely reliant on the OR ana- lysts to modify the schedule and, more importantly, to determine when the process was complete and the current schedule deemed acceptable.

Therefore, we are extending the model to provide two new capabilities to make the chief residents autonomous. First, we are redesigning the structure to enable the speciﬁcation of many new rules and requirements simply by modifying the input data ﬁles. Second, we are developing an algorithm that will generate a large set of promising Pareto-dominant candidate schedules from which the Chiefs can select.

This will make them more independent, lead to a long-term feedback loop, and provide a teaching mechanism that can be used to modify how candidate schedules are selected for review in the future.

Appendix This appendix provides the constraints needed to identify a feasible schedule. For more details, referto http://ioe.engin.umich.edu/techrprt/pdf/TR06- 06.pdf.

Notation–Sets •R—set of residents.

•R 2nd ⊂R—set of PGY2s.

•R 3rd ⊂R—set of PGY3s.

•D—set of days, indexed from 1 (July 1) to 365 (June 30).

•V⊂D—set of days requiring coverage at Hospi- tal B.

•D T⊂D—set of Tuesdays.

•DW⊂D—set of Wednesdays.

•M—set of months, indexed from 1 (July) to 12 (June).

Notation–Parameters •f m∈D—ﬁrst day of monthmfor allminM.

•f l∈D—last day of monthmfor allminM.

Variables •x rd=1 if residentris assigned to the primary call at Hospital B on dayd, else zero, for alldinDand allrinR.

•y rd=1 if residentris assigned to the backup call at Hospital B on dayd, else zero, for alldinDand allrinR.

•z rd =1 if residentris assigned to the call at Hospital C on dayd, else zero, for alldinDand all rinR.

•e d=1 if an EOC is assigned to the call at Hospi- tal C on dayd, else zero, for alldinD.

Constraints • (1) Residents cannot be assigned to more than one call per night:

x rd+y rd+z rd≤1∀r∈R d∈D • (2) All hospital coverage requirements must be met:

Cohn et al.:Scheduling Medical Residents at Boston University School of Medicine 194 Interfaces 39(3), pp. 186–195, © 2009 INFORMS (3) A resident cannot be on call more than once in any four-day period:

d∈ d d +3 xrd+ d∈ d d +3 yrd+ d∈ d d +3 zrd≤1 ∀r∈R ∀d ∈ 1 D −3 • (4) A resident cannot be assigned to more than ﬁve calls in any calendar month:

d∈ f m l m xrd+ d∈ f m l m yrd+ d∈ f m l m zrd≤5 ∀r∈R ∀m∈M • (5) PGY2s cannot be assigned to call on Tuesdays; PGY3s cannot be assigned to call on Tuesdays or Wednesdays:

x rd=0∀d∈D T r∈R 2nd y rd=0∀d∈D T r∈R 2nd z rd=0∀d∈D T r∈R 2nd x rd=0∀d∈D T∪D W r∈R 3rd y rd=0∀d∈D T∪D W r∈R 3rd z rd=0∀d∈D T∪D W r∈R 3rd References Aickelin, U., K. Dowsland. 2004. An indirect genetic algorithm for a nurse scheduling problem.Comp. Oper. Res.31761–778.

Aickelin, U., J. Li. 2007. An estimation of distribution algorithm for nurse scheduling.Ann. Oper. Res.155289–309.

Azaiez, M. N., S. S. Al Sharif. 2005. A 0-1 goal programming model for nurse scheduling.Comp. Oper. Res.32(3) 491–507.

Bard, J. F., H. W. Purnomo. 2005a. A column generation-based approach to solve the preference scheduling problem for nurses with downgrading.Socio-Econom. Planning Sci.39(3) 193–213.

Bard, J. F., H. W. Purnomo. 2005b. Preference scheduling for nurses using column generation.Eur. J. Oper. Res.164510–534.

Bard, J. F., H. W. Purnomo. 2005c. Short-term nurse scheduling in response to daily ﬂuctuations in supply and demand.Health Care Management Sci.8315–324.

Bard, J. F., H. W. Purnomo. 2007. Cyclic preference scheduling of nurses using a Lagrangian-based heuristic.J. Scheduling10(1) 5–23.

Beaulieu, H., J. Ferland, B. Gendron, P. Michelon. 2000. A math- ematical programming approach for scheduling physicians in the emergency room.Health Care Management Sci.3193–200.

Beddoe, G. R., S. Petrovic. 2006. Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering.Eur. J. Oper. Res.175(2) 649–671.Burke, E. K., G. Kendall, E. Soubeiga. 2003. A tabu-search hyperheuristic for timetabling and rostering.J. Heuristics9(6) 451–470.

Burke, E. K., P. De Causmaecker, S. Petrovic, G. Vanden Berghe.

2006. Metaheuristics for handling time interval coverage con- straints in nurse scheduling.Appl. Artiﬁcial Intelligence20(3) 743–766.

Burke, E. K., P. De Causmaecker, G. Vanden Berghe, H. Van Landeghem. 2004. The state of the art of nurse rostering.

J. Scheduling7441–499.

Burke, E. K., T. E. Curtois, G. Post, R. Qu, B. Veltman. 2008.

A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem.Eur. J. Oper. Res.188(2) 330–341.

Carter, M., S. Lapierre. 2001. Scheduling emergency room physi- cians.Health Care Management Sci.4347–360.

Cheng, B., J. Lee, J. Wu. 1997. A nurse rostering system using constraint programming and redundant modeling.IEEE Trans.

Inform. Tech. Biomedicine144–54.

Cipriano, R., L. D. Gaspero, A. Dovier. 2006. Hybrid approaches for rostering: A case study in the integration of constraint programming and local search. M. J. B. Aguilera, C. Blum, A. Roli, M. Sampels, eds.3rd International Workshop Hybrid Metaheurstics 2006 (HM2006).Lecture Notes in Computer Science, Vol. 4030. Springer-Verlag, Berlin-Heidelberg, 110–123.

Dias, T. M., D. F. F erber, C. C. de Souza, A. V. Moura. 2003. Con- structing nurse schedules at large hospitals.Internat. Trans.

Oper. Res.10(3) 245–265.

Ehrgott, M. 2005.Multicriteria Optimization. Springer, Berlin.

Franz, L., J. Miller. 1993. Scheduling medical residents to rotations:

Solving the large-scale multiperiod staff assignment problem.

Oper. Res.41269–279.

Gendreau, M., J. Ferland, B. Gendron, N. Hail, B. Jaumard, S. Lapierre, G. Pesant, P. Soriano. 2006. Physician scheduling in emergency rooms.Proc. 6th Internat. Conf. Practice Theory Automated Timetabling PATAT’06 , Brno, Czech Republic, 2–14.

Gutjahr, W. J., M. S. Rauner. 2007. An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria.Comp. Oper. Res.

34642–666.

Kellogg, D., S. Walczak. 2007. Nurse scheduling: From academia to implementation or not?Interfaces37(4) 355–369.

Landa Silva, J., E. K. Burke, S. Petrovic. 2004. An introduction to multiobjective metaheuristics for scheduling and timetabling.

X. Gandibleux, M. Sevaux, K. Sorensen, V. T’kindt, eds.

Metaheuristics for Multiobjective Optimization. Springer-Verlag, Berlin/Heidelberg, 91–129.

Li, J., U. Aickelin. 2006. BOA for nurse scheduling. M. Pelican, K. Sastry, E. Cant-Paz, eds.Scalable Optimization via Probabilis- tic Modeling From Algorithms to Applications. Springer-Verlag, Berlin/Heidelberg, 315–332.

Ozkarahan, I. 1994. A scheduling model for hospital residents.

J. Medical Systems18251–265.

Petrovic, S., G. R. Beddoe, G. Vanden Berghe. 2002. Case-based reasoning in employee rostering: Learning repair strategies from domain experts. Technical report, Automated Schedul- ing Optimisation and Planning Research Group, School of Computer Science and Information Technology, University of Nottingham, Nottingham, UK.

Sherali, H., M. Ramahi, Q. Saifee. 2002. Hospital resident schedul- ing problem.Production Planning Control13220–233.Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.

J. Oper. Res.60233–246.

Valouxis, C., E. Housos. 2000. Hybrid optimization techniques for the workshift and rest assignment of nursing personnel.Arti- ﬁcial Intelligence Medicine20155–175.

Vassilacopoulos, G. 1985. Allocating doctors to shifts in an accident and emergency department.J. Oper. Res. Soc.36517–523.

Janet Osterman, MD, Vice Chair, Education and Training; Director, Residency Training and Medical Student Education; and Associate Professor of Psychi- atry, Division of Psychiatry, Boston University School of Medicine, 850 Harrison Avenue, Dowling 7 South, Boston, MA 02118-4001, writes: “I am writing to ver- ify that the contents of the attached paper are correct.

Speciﬁcally, the 2007–2009 Chief Residents at Boston University School of Medicine, Carisa Kymissis, Justin Esses, and Niesha Westmoreland, under the supervi- sion of Dr. Janet Osterman, worked with Professor Amy Cohn and her student, Sarah Root, to develop the on-call schedule for psychiatry residents. Through the use of their mathematical programming skills and our interactions working on the project together, wewere able to effectively generate a year-long sched- ule simultaneously covering a diverse group of resi- dents stafﬁng three different facilities. In the past, this schedule had been created manually, resulting in a time-consuming and signiﬁcant burden to the Chief Residents. The solution that resulted using this man- ual technique not only failed to satisfy all of the resi- dents’ needs, but was often unsuccessful in satisfying all of the program’s requirements (for example, the number of days between call shifts to ensure adequate rest). This has ramiﬁcations not only in terms of res- ident satisfaction but also on their ability to provide high-quality patient care.

“In contrast, the schedule that this research pro- duced was not only far simpler for the Chief Resident, but also satisﬁed all strict requirements, granted all vacation requests, and was well received by residents in the program. It also freed up time that the Chief Residents could devote to teaching and other admin- istrative duties. We were extremely pleased with the outcome and hope to be able to use this tool in the future.”Downloaded from informs.org by [132.174.254.97] on 25 February 2017, at 11:26 . For personal use only, all rights reserved.