Case—Pediatrician Scheduling at British Columbia Women’s Hospital

1. Introduction

British Columbia Women’s Hospital (BCWH) is one of the busiest maternity care centres in Canada, delivering over 7,000 babies per year. It provides care to women from the Vancouver area as well as those experiencing high-risk pregnancies from anywhere in British Columbia. In addition to all of the regularly scheduled doctors and staff at BCWH, at every hour of every day, there is also a pediatrician on call, available to attend all deliveries (required at all C-sections and any vaginal deliveries involving risk factors or complications), examine newborn babies on the postpartum ward when issues arise, and look after infants admitted to the neonatal intensive care unit with a variety of medical issues (e.g., severe jaundice, feeding difficulties, blood sugar issues).

Meg, the lead scheduler for the on-call pediatric group, seeks your help to develop a computerized scheduling tool. The current scheduling process is manual and extremely labor intensive (no pun intended). Meg typically spends up to 20 hours finalizing each schedule, going through several iterations and back-and-forth communications with the team of pediatricians. It can be challenging enough to find a feasible schedule, let alone one that everyone is satisfied with. For example, there is often disagreement around how the shifts are scheduled and how equitable the schedule is (e.g., the day/night shift distribution). This is an emotionally draining process, as Meg tries to make all of her colleagues happy. Furthermore, she often absorbs shifts that her colleagues do not want or can no longer do just to avoid further iterations and potential conflict. In summary, the current process wastes a lot of Meg’s time, and she would love to automate the scheduling process.

2. Scheduling Details

Pediatricians are scheduled in four-week cycles, with each schedule typically released at the start of the previous cycle (i.e., four weeks in advance).¹ Pediatricians on call are assigned to either a day shift (7:30 a.m.–5:30 p.m.) or a night shift (5:30 p.m.–7:30 a.m.), with each shift requiring exactly one pediatrician. For each of the 4*7*2 = 56 shifts per cycle, Meg chooses someone from a pool of 15 pediatricians.

Based on discussions, Meg indicates that some system constraints are “must-haves,” whereas others would be “nice-to-haves.” The former, known as “hard constraints,” are based on safety and quality regulations and/or strong preferences the pediatric group has. The nice-to-haves, also known as “soft constraints,” would be ideal to satisfy if possible, as they improve pediatricians’ work-life balance. However, the group understands and accepts that some violations of these constraints may be necessary to achieve a workable schedule. The hard and soft constraints are summarized as follows:

2.1. Hard Constraints

1. Every shift must have exactly one pediatrician.

2. Pediatricians have a predetermined number of shifts they are supposed to work each cycle (with the sum over all pediatricians equaling the 56 shifts of the four-week cycle). Meg provides that information in a separate Excel file that comes with this case.

3. Pediatricians cannot work back-to-back shifts (i.e., no one works 24 hours in a row).

4. Pediatricians cannot work consecutive night shifts (i.e., someone assigned to work Tuesday night cannot be scheduled to work that Monday or Wednesday night).

5. Pediatricians cannot be scheduled for more than two shifts in a given weekend (weekend shifts are Friday night, Saturday day and night, and Sunday day and night).

6. Pediatricians should not be scheduled on any shifts they requested off. These requests are also provided in the Excel file.

   Also, BCWH recently instituted a Pediatrician of the Week (POW) process in which one pediatrician serves in a lead role each week (considered as Monday through Sunday). As it relates to scheduling, the following are hard constraints around the POW process:

7. Each week requires one pediatrician to serve as POW.

8. The POW must cover (at least) the following shifts: Tuesday day, Thursday day, and Saturday night.

9. No one serves as the POW more than once in a four-week cycle.

10. Each pediatrician has a designated number of times they should be the POW over the course of the year (also indicated in the Excel sheet). Therefore, anyone who has already completed their requirements should not be assigned as POW for any week in the current planning cycle.

2.2. Soft Constraints

1. Pediatricians prefer not to work on consecutive weekends.

2. In addition to the hard constraint of pediatricians not working consecutive night shifts, they also prefer not to work night shifts two days apart (e.g., if someone works Monday night, then ideally they do not work the Saturday night two days prior nor the Wednesday night two days later).

3. Pediatricians prefer not to work more than two evening shifts in a given work week.

4. The pediatric group seeks equity in day versus night shifts; that is, each pediatrician’s workload should ideally be evenly split between day and night shifts during the cycle.

3. An Optimization Approach

A mathematical optimization problem has three main components: (1) an objective, (2) decision variables, and (3) constraints. The natural decision variables for this problem are which pediatricians to assign to which shifts, for each of the 56 shifts in the cycle, as well as which pediatrician should be designated as the POW each of the four weeks. We described the constraints of the problem in the previous section. But what is the objective?

For reasons outside the scope of the problem (e.g., seniority, training, research versus clinic time), the total number of shifts expected of each pediatrician over the year, and for the next cycle in particular, has already been determined. There are no financial considerations to be considered at this point, so in some sense this is a problem without any natural objective (e.g., “maximize profit” or “minimize cost”).

Meg tells you that she simply wants a schedule that meets all of the hard constraints and comes as close to meeting the soft constraints as possible. A common way to solve problems with hard and soft constraints is to relax the soft constraints in a way that allows them to be violated while introducing penalties for violations in an objective function. We illustrate this concept through a different problem before asking you to apply these ideas to the present case.

Consider a small-sized version of the famous “Diet Problem” (Stigler 1945, Dantzig 1990). This version will be completely unrealistic but will illustrate the concept of soft constraints and how to incorporate them into an objective function. Assume someone eats only two foods each day, apples and bananas. Their daily goal is to consume 2,500 calories, 30 grams of fiber, 70 mg of vitamin C, and 3,400 grams of potassium. They are not concerned about costs; they just want to come “as close as possible” to satisfying their goals. In fact, there are so many examples of this “goal satisfaction” objective in practice that they form their own special class of optimization problems, known as “Goal Programming.”

The following table provides the contribution of apples and bananas (per 100 g) to the different goals and the ideal totals for each of them.

Table

Not surprisingly, the implied system of four equations with two unknowns has no feasible solution. By softening the nominal requirement of meeting all goals exactly, we can formulate a problem that yields a feasible solution but penalizes the amount by which the goals are violated. Specifically, letting x₁ and x₂ be the quantity of apples and bananas consumed each day, respectively (in hundreds of grams each), we can formulate the diet problem as follows:

Note that the primary decision variables (x₁ and x₂ for apples and bananas, respectively) do not appear in the objective function; because we are not considering the cost of obtaining them, they just appear in the goal constraints around total calories, fiber, vitamin C, and potassium, respectively (Equations (1)–(4)). The u_i and o_i variables in those constraints represent the amount by which the left-hand side is under or over the right-hand-side target, respectively. The objective function allows for different penalties for being under versus over the right-hand side of each constraint. For example, $w_{u1}$ is the penalty per calorie under the calorie target, whereas $w_{o1}$ is the penalty per calorie above it. The objective function in combination with the fact that the u_i and o_i variables are nonnegative make it so that at most one of u_i and o_i will be positive for each constraint i. If one cares about being under versus over equally, then by setting $w_{ui}=w_{oi}=1$ for each i, the objective function minimizes the sum of absolute differences between the left- and right-hand sides of all constraints. If instead one sets $w_{ui}=w_{oi}=1/b_i$ for each i, the objective function minimizes the sum of absolute proportional differences between the left- and right-hand sides.

Although the point of this example was the development of the formulation above, you may be wondering what the solution is. By letting $w_{ui}=w_{oi}=1/b_i$ for each i, Solver indicates that this individual should consume 327 grams of apples and 852 grams of bananas per day. In doing so, they will meet their fiber and potassium goals exactly, fall short of their calories goal by 63%, and exceed their vitamin C goal by 27%. The 63% shortfall on calories may be a surprising and unreasonable outcome. This suggests that we may want to consider a nonlinear cost function for the deviations. If we consider a piecewise linear convex cost structure, we can still solve the problem as a linear program. Further discussion of this extension is beyond the scope of this case.