A Review of the Scheduling Problem within Canadian Healthcare Centres

Abstract

In this paper, the current literature regarding nurse scheduling and physician scheduling in Canada is reviewed. Staff scheduling is a vital aspect of healthcare which has immediate positive benefits when optimized. It is also a very complex optimization problem, often involving conflicts, human evaluation and time constraints. Four categories of problems are reviewed: staff scheduling, physician scheduling, operating room scheduling, and outpatient scheduling, each focusing on a different aspect of resource scheduling and involving unique considerations. Numerous different heuristics and algorithms have been implemented and tested in dozens of hospitals across Canada with nearly universal positive results. Despite the obvious benefits, continued implementations of the optimization software is uncommon.

1. Introduction

The scheduling problem in hospitals is a difficult problem to address, but an important one. Given the recent rise of COVID-19, this has been increasingly important as it has shown how limited resources are. In Canada, during the initial outbreak, many hospitals nationally were pushed to their breaking point with all elective surgeries and a large portion of visits being cancelled in attempts to alleviate the traffic. This could have, in part, been reduced with better utilization of their resources. Many outpatients were turned around at the door and staff were made to work long stressful hours. Additionally, many staff in Canadian hospitals are underwhelmed or disappointed with their schedules and are actively in need of a better solution. Surveys have shown that 24.5% of physicians are not satisfied with their careers due to the stress they are put under [1], operating rooms are only used at 68% of their potential on average [2], and at the Ottawa hospital residents report that the worst task they are assigned is creating schedules by hand [3]. These are just a few anecdotes, but they highlight the demand for better scheduling that exists within Canadian hospitals. With more efficient rostering, they could both allow more patients to access the care they need and alleviate some of the work that the staff needs to do.

The focus is on Canadian papers in particular as Canada performs poorly on several important metrics. Canada is ranked ninth out of 11 when compared to other high-income countries [4]. In 2017, Canada had far fewer physicians overall compared to the international standard with 2.7 per capita compared to 3.5 [5]. Additionally, among Canadian physicians, over 5/6ths meet the requirements for burnout [6]. They were also over three times more likely to show signs of depression [6]. It is known that when scheduling improves, so does both patient outcomes [7] and staff wellbeing [8]. By understanding how scheduling is done and exploring how to improve, healthcare in Canada can improve.

This leads to the next problem that comes with scheduling: its complexity. Scheduling is an NP-Hard problem. The search space for creating a schedule grows exponentially so finding an efficient solving technique is a challenge. When creating a schedule there are often dozens of constraints and an uncountable number of candidate solutions. With every new staff member, appointment, or rule, the time needed to find a solution increases exponentially. Furthermore, finding the optimal solution is not always possible due to time constraints of computing limits, so one often has to settle for a roster that is only satisfactory. This can mean either cutting the algorithm short or applying additional metaheuristic algorithms to improve solutions until they are acceptable. Many papers have attempted to develop strategies and software to address these problems, but given the large variety of use cases, this has led to a large variety of solutions.

There are four main categories of hospital scheduling problems that are often looked at in Canada. The first of these categories is about how to schedule the staff. Hospitals need nurses, specialists, students, residents, etc., to be on the floor every day. The second type involves scheduling physicians to work in the emergency rooms. This is typically separated from general roster scheduling, as the addition of the emergency room adds additional considerations and it is typically more important due to the nature of the work. The third topic that is often reviewed is how to schedule operating rooms to be used. Operating rooms are one of the most important resources a hospital has, and therefore needs to be handled appropriately. Finally, the last category covers how to schedule outpatients and appointments. Given these distinctions, Section 4 will cover each of these scheduling topics in-depth and how they have impacted Canadian hospitals. Section 2 gives our methodology for selecting the papers. Section 3 will give a brief overview of some of the considerations that go into creating a schedule that applies to all methodologies. Section 5 will review the tools and software that made each of these possible. Section 6 will cover what should be looked at in the future to better allocate and utilize resources in scheduling and in Section 7 we will conclude the findings.

The author’s contribution is as follows: We have conducted a literature review on nurse and physician scheduling with a focus on Canadian-specific papers. Our selection criteria are outlined in Section 2. We have summarized and analyzed their contributions below in order to help better understand the current state of the literature.

2. Methodology

Papers were found using major search engines and through publishers including Google Scholar, IEEE Explore, Research Gate, Elsevier, Springer, and the Omni database [9]. As this is primarily an operations research topic, operations research journals were investigated thoroughly. In addition, in order to fully capture the entire perspective, papers from the domains of computer science, engineering, and medicine. The following journals and conferences were reviewed: Operations Research for Health Care, Canadian Medical Association, INFORMS Journal on Applied Analytics, Telecommunications and Signal Processing, IIE Transactions on Healthcare Systems Engineering, Production and Operations Management, Canadian Journal of Surgery, International Journal of Production Economics, Expert Systems with Applications, International Conference on Computing & Communication Technologies, Institute for Operations Research and the Management Sciences, Health Care Management Science, Health Systems, Annals of Operations Research, IEEE Explore, PATAT (Practice and Theory of Automated Timetabling), Decision Support Systems, Omega (United Kingdom), Journal of Medical Sciences, Production and Operations Research, Expert Systems with Applications, Principles and Practice of Constraint Programming, Machine Learning for Health, and European Journal of Operations Research. These journals were chosen as they contained papers which met all of our criteria. The journals were found through citations and the above mentioned search engines. If a journal is not mentioned we did not find a paper which met the requirements.

Papers were filtered based on location, date, and focus. In order to be accepted the paper must either have come from a Canadian university or worked directly with a Canadian hospital. Papers that were more recent were also weighted higher than those which were older. We made sure to have at least 8 in each category. About half of the papers are from the last 5 years with the oldest being from 1987. The selected papers needed to present an implementation for an optimization model and presented the results. Additionally, supplementary algorithms such as discrete simulation models were accepted if they directly contributed to creating a schedule.

Over 100 papers were reviewed to ensure that this selection is encompassing of the domain we wish to survey. This review involved an initial read to ensure that they were relevant to the problem. These 100 were filtered to approximately 75 papers that mentioned Canadian healthcare, of which 40 worked with Canadian hospitals. The 40 which worked with Canadian hospitals were then thoroughly read and surveyed below. We believe these represent the literature’s current state of improving scheduling within Canadian healthcare centres. Papers beyond the 40 were discarded as they did not meet the standards.

3. Schedule Overview

3.1. Problem Definition

The assignment problem is the most basic version of scheduling. It is simply the problem of assigning tasks to agents in a one-to-one fashion. Every agent gets one and only one task. The goal is to minimize the total cost. This can be interpreted as finding the minimum weighted bijective graph. Formally, Given a set of agents called AGENTS and a set of tasks, which is a function that takes an agent and is denoted by f, one wants to minimize the equation which takes in the agent and the task the agent is mapped to:

$$min\sum _{\forall a\in AGENTS}C(a,f\left(a\right))$$

(1)

In the above Equation C is the cost function of an agent and the task it was assigned.

The scheduling problem expands on the assignment problem by introducing additional constraints that must be satisfied. The variation of scheduling determines the constraints, I.E, nurse scheduling schedules nurses to shifts with the appropriate constraints. The new problem can be formally defined as follows. Let C be the cost function, A be the set of agents, T be the set of tasks, and H be the set of all constraints:

$$min\sum _{\forall a\in A}C(a,f\left(a\right))$$

(2)

$$s.t.h(a,t)\forall a\in A,t\in T,h\in H$$

(3)

This can again be further generalized by the addition of soft constraints which do not need to be satisfied in order to be feasible but instead incur a penalty in the objective function.

In this paper, the terms rostering and scheduling will be used interchangeably. More generally, a schedule is a chronological series or list of events and assignments for an individual or organization. A scheduling problem is an optimization problem which involves finding how to efficiently and accurately create said schedule based on the constraints the job requires; this is an NP-Hard problem in the field of operations research. Some variations of the scheduling problem have their decision problem equivalent known to be NP-Complete [10]. Each problem comes with a unique set of constraints and each solution requires a different degree of optimality. This leads to a wide variety of methods and techniques being used to solve the problem based on a variety of starting points. The problem that is constructed is what is the optimal way to create a schedule given a starting point and a set of constraints. The constraints vary per problem. When scheduling nurses, holidays and the number of hours worked could be considered constraints. On the other hand, when scheduling appointments, the urgency of pathology would be the main consideration.

Many of the techniques laid out in the following paper can be used to solve both of these types of problems.

In the following papers, the types of scheduling can broadly be divided into 2 categories. These are not meant to be strict divisions but are helpful to note. The first type of schedule, type one, is deterministic and static in nature. This means that the resource they are scheduling is known in advance and will not change in the future. They are typically created weeks before they are needed and this period is known as the planning period. Staff scheduling problems are a common example of this type. The second type of schedule, type two, is stochastic and dynamic. These schedules often have incomplete data and either need to impute the data, simulate the data or update the schedule as new data comes in. In the latter case, the schedule is always being updated instead of being recreated. The random aspects of these schedules make searching for near-optimal schedules near impossible. Outpatient scheduling falls under this type of schedule, with the probabilistic elements coming from the randomness of patient arrivals and cancellations. These types of schedules can then be further decomposed into four additional problems in the healthcare domain. They are as follows:

• General Staffing/Nurse Staffing: This type of scheduling is general roster scheduling. Hospitals need staff and staff need to be scheduled. This is mostly applied to nurses but the ideas are applicable to any type of staff.
• Emergency Room Scheduling: This is very similar to medical staff scheduling but has the added caveat that physicians must be scheduled with the knowledge that the workload is variable. The emergency room occupancy has stochastic elements regarding the amount of work the emergency department is predicted to have. This domain looks into both online and offline schedules depending on their use case.
• Operating Room Scheduling: This type of scheduling is very broad and can fall under both types of schedules. On the ond hand, operating rooms and surgeons can be treated as resources and must be allocated as they need them. This would be deterministic in nature and similar to emergency room scheduling. However, operating rooms also have to deal with scheduling patients within the operating room and likewise, in emergency rooms, it is impossible to know the demand prior to creation. As demand for the operating room can fluctuate and different priorities exist it is difficult to plan a schedule for it upfront.
• Outpatient Scheduling: Outpatients are patients that do not stay at the hospital overnight. These patients typically arrive either through the emergency room or call ahead to book an appointment. This leads to a dynamic schedule as cancellations and arrivals can happen at any time. Often scheduling is designed such that there is an ongoing schedule that is consistently updated. Since outpatients are a primarily stochastic resource they fall comfortably into type two.

3.2. Programming Models and Solving Techniques

Every rostering problem begins with a mathematical programming problem. This is a construction of an objective function and the constraints which must be satisfied. What makes each problem unique is which constraints each one has and the novel methodologies they employ to solve the problem. Many of these models aim to specialize in a specific area of expertise. Others try to generalize the models to be utilized outside of the specific domain they originated. Despite the variety that each model contains some constants appear throughout most of the papers. Instead of repeating them for each category, here is a broad overview.

One notable idea is the difference between a mathematical programming model and a constraint programming model. Mixed-integer models (MIP), linear programming models (LP), integer models (IP), etc. are all examples of mathematical models. In a sense, all of the above are constraint programming models as they intend to optimize an objective function based on constraints but there is a distinction. Constraint programming models have the same structure as mathematical programming models but their constraints are far less restricted, while mathematical programming models are restricted to inequalities and equalities, constraint programming models may have constraints in any form. Examples would include but are not limited to, logical constraints such as AND or OR, and arithmetic constraints such as a modulo. By loosening the restrictions on the constraints it changes how the problem is approached and solved.

After a model is defined, it is solved using a solving algorithm, hereby denoted as a solver. One distinction is the dichotomy of exact and heuristic methods. Exact methods search for the optimal solution and are guaranteed to find it after an unspecified amount of time. This is typically infeasible however as all problems presented here are NP-Hard and have exponential or worse growth as the scale increases. Heuristics offer a tradeoff of time for solution quality. Many heuristics are able to get near-optimal solutions much faster than exact algorithms but have no guarantee of optimality. That is not to say that optimal solutions cannot be found, however. The most common exact method is mixed integer linear programming (MIP). Heuristics include local search techniques such as Tabu search [11] and particle swarm optimization [12]. Figure 1 shows the distribution of methodologies used in the papers found in Canadian healthcare literature. There has been continuous work on solvers since their inception in order to improve efficiency. Typically, papers that want to create generic programmable solvers tend to use constraint programming, while papers that directly create solvers tend to make mathematical models.

The first commonality is the constraints. The constraints are often broken down into specific categories and classes. One common distinction is the difference between hard and soft constraints. Hard constraints are constraints that must be fulfilled for a solution to be feasible. A typical example would be that each nurse must work no more than 10 days every two weeks. A soft constraint is a constraint that would like to be satisfied but is not mandatory. Instead, it incurs a penalty to the objective function based on how far away from being satisfied it is. A typical example would be that nurses with the same specialty should not work on the same day, while it’s not optimal to have multiple nurses with the same specialty working, it is not necessarily detrimental either.

The second distinction that appears in papers such as Bourdais, Galinier, and Pesant [13], Beaulieu et al. [14], Patrick et al. [15], Rousseau, Gendreau, and Pesant [16], Gendreau et al. [17], etc. are the categories below:

• Supply and Demand Constraints

  -

  Rules pertaining to demand of shifts and availability of staff.

• Workload/Availability Constraints

  -

  Rules pertaining to how much each staff work.

• Distribution Constraints

  -

  Rules regarding the distribution of shifts.

• Ergonomic Constraints

  -

  Rules regarding the pattern that shifts take.

Most patterns of constraints can be generalized into these categories or a subset of these categories. They enable the authors to make sweeping generalizations about the constraints and abstract them. When developing a solver, this process allows developers to make generic solvers. A generic solver allows implementations of constraints without having to manually recreate the underlying model. Some papers, such as the one by Bourdais, Galinier, and Pesant [13], use these distinctions as a base to create a domain-specific language (DSL) for their software. In other words, a user can input their own constraints and customize the underlying model. This process is far less popular than creating a specific solver however as seen in Figure 1.

Another concept that is brought up a lot is the difference between a cyclic and an acyclic schedule. Cyclic schedules function as a way to create repeating schedules and reduce the search space. They are schedules that are designed to be looped, and so they must satisfy constraints as if they were repeated. There are two kinds of cyclic schedules: ones with rotation and ones without. Cyclic schedules with rotation include the option of alternating between a set of schedules in a pattern while cyclic schedules without rotation merely repeat the same schedule indefinitely. Carter et al. [1] introduces this idea and creates all three kinds of schedules. He is quick to note that cyclic schedules cannot account for personal preference and that it is the staff’s responsibility to trade shifts among themselves to achieve this. They also created an acyclic schedule which takes longer but tends to create more personalized rosters. The repeating nature of it makes it hard to include more rules and as such, it is not the preferred option when creating schedules.

A consistent theme in many of the papers is that some are not solely done for research, but rather to demonstrate the efficacy of a product. Some papers, such as the one by Bourdais, Galinier, and Pesant [13], Rousseau, Gendreau, and Pesant [16], White and White [3], White et al. [18], and by Patrick et al. [15] aim to create software to help hospitals with the scheduling problem and to demonstrate the mathematical programming model that drives it.

Following that, many papers start with a specific view in mind such as Rosenbloom and Goertzen [19], Bourdais, Galinier, and Pesant [13], Patrick et al. [15], and Beaulieu et al. [14]. They look into problems at a specific hospital with a specific set of rules. Other papers, such as the ones by Jaumard et al. [20], Gendreau et al. [17], Naderi et al. [21], Bourdais, Galinier, Pesant [13], Carter et al. [1], and Rousseau, Gendreau, and Pesant [16] then try to approach the generalized problem so that they can be used in more hospitals and departments. This involves abstracting the concrete rules and instead trying to make them usable in any hospital. General problems are often larger and more complex, so solving them becomes a problem in itself. Even still some papers focus on aspects of model creation besides the model itself. These papers try to forecast variables or build frameworks for the model such as the papers by Godin and Wang [22], Drysdale, Singh, and Goldenberg [23], Savage et al. [24], Rozario and Rozario [25], and Azari-Rad et al. [26]. The distribution of paper focuses can be seen in Figure 2.

4. Hospital Scheduling in Depth

4.1. General Staffing/Nurse Staffing

The general staffing/nurse staffing problem is the most straightforward type of problem presented and is likely what comes to mind when presented with scheduling. This problem represents the most clear-cut version of a type one schedule. It involves creating a schedule for the staff to determine when to work, and in some cases where to work. This type of problem typically involves having all information known upfront and allows a large amount of time to create the schedule. Often a planning period of two weeks to a month is designated and a new roster needs to be created at the end of every period. This leeway allows cyclic schedules to be created to reduce the amount of times schedules must be generated and to reduce the feasible search space. Hospitals will often create these schedules weeks in advance to allow nurses and other staff to plan for the upcoming week.

Table 1. General Staffing/Nurse Staffing Papers.

Paper	Methodology	Data
Rosenbloom and Goertzen 1987 [19]	Cyclic Integer programming	N/A
Jaumard et al., 1998 [20]	Generalized linear programming, Column Generation	Royal Victoria Hospital of Montreal
Bourdais, Galinier, and Pesant 2003 [13]	Constraint programming, Heuristics Search	Montreal-based hospitals
White and White 2003 [3]	Tabu Search	Ottawa Hospital
White et al., 2007 [18]	Tabu search, Great Deluge, IDWalk	Ottawa Hospital
Legrain, Bouarab and Lahrichi 2015 [27]	Excel Based Heuristic	Notre-Dame and Sainte-Justine
Patrick et al., 2019 [15]	Linear Programming	Ottawa Hospital
Legrain, Omer, and Rosat 2020 [28]	Linear Programming, Column Generation	N/A
Zimmerman et al. [29]	MILP, Simulation	Vancouver Coastal Health

summarizes the contributions to nurse scheduling and where they were implemented. Constraints and considerations will vary between departments and hospitals but many are consistent throughout.

4.1.1. Constraints

Constraints for general hospital staff scheduling are very straightforward. Examples of the constraints are listed below:

• Supply and Demand Constraints

  -

  A schedule must be created every two weeks [19,20].

  -

  No specialties need to be covered on specific days [15].

• Workload/Availability Constraints

  -

  Nurses must have 10 shifts [19].

  -

  Pathologists must be assigned no more days than their FTE specifies [15].

  -

  Pathologists must be scheduled to one of their subspecialties [15].

  -

  Medical staff may take vacations at any time [3].

  -

  Staff must not exceed seven calls within a 28 day planning period [3].

• Distribution Constraints

  -

  Nurses cannot be schedules split weekends [19].

  -

  Nurses must be allowed one weekend off [19].

  -

  Pathologists cannot be scheduled two subspecialties in a day [15].

  -

  Pathologists should be scheduled different subspecialties in adjacent weeks [15].

  -

  Calls should be evenly spaced [3].

• Ergonomic Constraints

  -

  A nurse cannot work more than six days in a row [19].

  -

  All working periods must be a minimum of three days consecutively [19].

  -

  A nurse may have an unlimited number of consecutive days off [19].

  -

  Only certain subsets of subspecialties are allowable at the same time [15].

4.1.2. Papers

Rosenbloom and Goertzen [19] dedicate their paper “Cyclic nurse scheduling” to creating a cyclic schedule for nurses. Nurses need to be scheduled around the clock and in a consistent manner so they are the perfect candidate to try cyclic scheduling. To demonstrate the effectiveness in search space reduction they go through the process of how the schedule is encoded. We will go over it here, as this is the way most schedules approach it. A schedule is defined as a string of binary characters representing the timeslot that a nurse would work. A ‘1’ would represent a shift, while a ‘0’ is the lack of one. In the case of this paper, there are 7, one for every day of the week. Other papers may go into the finer grain as they want to designate shifts at specific times. After, they then define the constraints that the schedule must obey, as seen above. This is known as the position-based approach.

Working under these constraints acyclically brings the total possible solutions down to 22 candidates. The rules for a cyclic schedule are then introduced, which further reduces the solution pool to six possible solutions. It is not specified but they use cyclic schedules with rotation, meaning schedules can alternate but will have to repeat eventually. Building a cyclic schedule comes with some benefits. Firstly, the approach is very fast and very small. The total implementation was done on a 64 K 8-bit computer. Another benefit to cyclic scheduling is it is inherently repeating. This means that the schedule only needs to be solved one time as opposed to every period. In practice, constraints will change and schedules will have to be remade but this minimizes the creations. Finally, this approach is flexible to the constraints. Constraints can be added and removed at will and the model will still perform. This paper does not specifically test their model on any real-world data.

For an example of a broader scope nurse scheduling model, we can look at “A Constraint Programming Application to Staff Scheduling in Health Care” by Bourdais, Galinier, and Pesant [13]. In their paper, they have two different goals in mind. The first is to create software called Hibiscus which can be used to create rosters for staff scheduling problems in a flexible manner. The second is to create a modular architecture that allows heuristic searches to be implemented into the model. Hibiscus is designed to be generic so that it can be utilized in many different scenarios without having to redesign it from the ground up. To begin addressing this goal they define the main rule divisions: demand, availability, distribution, and ergonomics. Doing so not only allows Hibiscus to be able to talk about classes of constraints but it makes them more straightforward to implement. These implementations allow them to implement a large variety of constraints such that the software is flexible enough to be adopted into other hospitals.

In an attempt to improve their model and make it stand out, they also introduce search heuristics to it. Bourdais, Galinier, and Pesant [13] have developed a framework that allows each constraint an associated incentive heuristic. The incentive heuristics act as modifiers. They are scored with potential assignments and then collectively they are added to the constraint dynamically. They work for all constraint types and allow greater control over how the model behaves.

Zimmerman et al. [29] approached the Vancouver Coastal Health network to partner with a community health centre and attempt to improve access for marginalized people. They worked with staff directly to create a three stage approach.

The first step in their process is to create an optimal weekly schedule using an MILP model. They solve the model using Gurobi, not going into the details of the solving process. Their model attempts to incorporate a multitude of ruels for creating the schedules. Shift length, breaks, and administrative duties are all considered.

The second part of their 3 part framework is a heuristic which tries to account for fluctiations in hours on a weekly basis. After creating an optimal schedule using the ruleset prior, a heuristic removes shifts until weekly schedules are fairly distributed amongst staff. The heuristic first identifies which shifts can be removed with minimal disruption. They then further filter the shifts based on the amount of overlap. If there is only 1 shift it is removed, otherwise one is chosen at random. This process is repeated until a sufficient number of shifts are removed.

The final step is a simulation model. This model aims to capture the variability of real world data, such as walk ins, no shows, and bookings. This is done through a homogeneous Poisson process.

Their model was able to better allocate shifts without increasing the work load for the nurses. These benefits can help improve access and care recieved my marginalized people.

The final model was tested using data collected from several Montreal hospitals. To evaluate how good a model performs six main characteristics are utilized:

• Coverage: Are the needed shifts covered?
• Quality: Does the model have good working conditions and follow hospital rules and preferences?
• Stability: Are the schedules homogeneous?
• Flexibility: How does the schedule deal with transitioning from the previous to the newer schedule?
• Fairness: Are shifts distributed fairly?
• Cost: How many resources are required to create and then implement the schedule?

The Hibiscus model had full coverage of scheduling. Quality and Fairness depend on the implementations of the constraints, but with search heuristics and the option to set hard vs. soft constraints it can achieve a reasonable quality. The model is also malleable when preparing for the transition period giving it stability. The model is flexible, although they admit that the search strategy is the least robust aspect and has room for improvement. Finally, the model has a low cost since human resources are not needed for creation, and computation is quite fast.

Another generalized model comes from Jaumard et al. [20] in their paper “A generalized linear programming model for nurse scheduling”. The incentive for generalizing the models comes from creating rosters that are more realistic and pragmatic given real-world situations. Their approach to generalization leads to a very complex and large mixed-integer programming model that cannot be solved in a reasonable time without decomposing the problem. To address this, they use a decomposition technique known as column generation. Column generation involves starting with a subset of the features and adding in relevant ones that most move the answer in the optimal direction one at a time. It was first proposed by Ford and Fulkerson in 1958 [30]. The starting problem is known as a master problem, and the problem which determines the effect of adding a new column is known as an auxiliary problem. Their master problem is the MIP model, and the auxiliary problem they introduce is a resource-constrained shortest path problem. Each path represents one of the columns to be added to the master problem. To solve this problem they use branch and bound. Branching can be done on master problem variables and auxiliary problem variables, but they found it was more efficient to use the latter. Each branch of the branch and bound method adds a new column to the master problem to be considered until a satisfactory solution is found.

A simple heuristic for nurse scheduling comes from Legrain, Bouarab and Lahrichi [27]. The motivation for this contribution is the prevalence of manual schedules or expensive commercial products. To contrast these two options, the authors propose a methodology that can be implemented at little to no cost on excel but with claims it can compete with CPLEX. They first introduce the 2 teams that will be scheduled, the main team and the float team. The float team is there to supplement the main team should it be needed and as such has much fewer restrictions. The main team heuristic begins by inserting nurse preferences and requests and then calculating a score, which is the gap between the needed number of nurses and the current number. From here nurses are inserted into shifts iteratively based on which shifts have the highest surplus and shortage. This is repeated until the score plateaus, in which a local search algorithm is employed with flip neighbourhoods to improve the schedule further. The float team heuristic is much simpler, relying of searching permutations to minimize the objective. The heuristic was able to capture more preferences and fewer alternating shifts with an equal equity to CPLEX, while still having a much faster run time to manual implementations. Two hospitals, Notre-Dame and Sainte-Justine were contacted to learn about the constraints and results needed to improve on current techniques.

Jaumard et al. [20] tested their model on data from the cardiology department of the Royal Victoria Hospital of Montreal. This hospital has a six-week planning period and had 41 nurses to schedule. Using their technique they were able to produce a good solution in about 16 and a half hours. This is if no violations were permitted and resulted in a solution within 1% of optimality. If linear relaxations were allowed a solution could be found in as little as 40 min.

Legrain, Omer, and Rosat [28] focus on dynamic nurse scheduling, presenting an algorithm that came second in the international nurse rostering competition. Dynamic nurse scheduling involves creating a schedule without perfect knowledge of the problem. Instead, the schedule is initially solved with the given information and updated iteratively as new information comes in. To solve the static problem they used free open source mixed integer programming software based on column generation. The dynamic algorithm they designed is a primal-dual algorithm which generates candidate solutions. These candidate solutions are then graded according to a sample average approximation algorithm. Their algorithm was the most robust in the competition that year, producing feasible and near optimal solutions in for most instances.

Patrick et al. [15] takes a step back from nursing and looks into determining what constraints need to be satisfied when it comes to scheduling pathologists. Pathologists require more considerations as they can be scheduled based on their specialization(s). The paper defines three ways this can be done. Either all pathologists have no specialization, each pathologist has a unique specialization, or each pathologist has more than one specialization. In 2010 the Ottawa Hospital switched from the first case to the third case, and it led to much higher turnaround times, as the specialization was not based on what was needed but rather what the pathologist preferred. In 2013, rules were put in place to ensure that pathologists were scheduled to subspecialties that were needed. This greatly reduced turnaround times, but protected time for research was neglected which led to low retention of staff. As such, a schedule designed for this specific ruleset was needed.

In addition to building the schedule, Patrick et al. [15] goes into what makes a schedule “good”. The metrics that were settled on are as follows:

• Missed Assignments: Schedules should maximize the subspecialties that are available in each time slot.
• Idle Time: If a pathologist is working, they should be assigned a fair and useful subspecialty.
• Back-to-back Weeks on the Same Specialty: The schedule should vary subspecialties between weeks.
• Overloaded weeks: The schedule should minimize the number of overloaded weeks.
• Consistent Assignment Within a Week: Within a week a pathologist should have the same subspecialty.
• Rotation Between Subspecialties: Pathologists should be scheduled to all of their subspecialties regularly.

The model was then implemented and compared to the manual schedules that were being created. Using a weighted sum of the above metrics the new model was able to boast a 56% to 77% improvement, all with solutions being generated in approximately two minutes. The model was able to universally decrease, or keep constant, the number of missed assignments, back-to-back weeks, overloaded weeks, late starts, early stops, and days below target. The model was tested using parameterized weights for each of the objectives listed above. The goal was not to find the optimal solution, just one that is sufficiently better than manual creation, so the authors recommend tinkering with the weights to improve any aspect of schedule creation that is unsatisfactory. The new schedule reduced scheduling time from 30+ h to >1, was far more flexible when presented with new constraints such as sick days or vacation days, addressed the original problem by allowing protected research time, and was generally more accepted by the pathologists.

The last papers in this section will be by White et al. [18], and White and White [3], which both take a look at the problem of scheduling students alongside doctors.

To start, “Scheduling Doctors for Clinical Training Unit Rounds Using Tabu Optimization” by White and White [3], looks into tabu optimization to create a schedule to be used at the Ottawa Hospital. They start by establishing the rules which make this schedule unique. Shifts consist of a senior staff member, and a junior or student if any are available. Optimally a shift should contain two juniors and two students, but with the shortage of staff, that is unlikely. To incentivize this, a table of penalties is used. If one student is missing a penalty of ‘5’ is incurred, while if two students are missing the penalty is ‘20’, etc. Furthermore, constraints that are common to general roster scheduling are used and listed above.

To improve the model’s solution, tabu search is used. A candidate solution is created using a bin packing algorithm and then other constraints are enforced using a backtracking algorithm. After a suitable candidate is found tabu search is performed. Tabu search is a metaheuristic algorithm that allows the user to search for nearby solutions. It was first formalized by Glover in 1989 [11]. It first defines a neighbourhood and allows actions on a solution such as a swap to traverse the neighbourhood. The main selling points for tabu search are that it has a memory that allows it to remember previous solutions. Additionally, tabu search accepts solutions that may be worse than the current solution in the name of exploration. This ensures that no model can be trapped in a local minimum/maximum. The first neighbourhood action that is defined is the ability to swap seniors, juniors, and students. After tabu minimization is performed the schedule is analyzed to determine if removing a student could improve the solution. Too many students can lead to a poor working environment. After this is done, the second neighbourhood action is defined: a rotation. This swaps the teams as a whole. This process is repeated until suitable solutions are found.

The paper then goes on to recommend post-optimization processing. There are considerations such as sick staff that the algorithm does not take into account and so must be plugged in by hand. Even still, however, it has been in use at the Ottawa hospital for approximately 18 months.

The other paper, “An Evaluation of Certain Heuristic Optimization Algorithms in Scheduling Medical Doctors and Medical Students”, by White et al. [18] attempts to solve the same problem. This paper focuses on expanding upon the method of improving the solutions generated by the model. They try four different models and evaluate which one performs the best. The first model is tabu search with a fixed tenure. Tabu search tenure describes how many data points are held in memory. This solver has a tenure of 5. The actual algorithm is the same as mentioned in the previous paper. The second metaheuristic algorithm is tabu search with random tenure. The tenure was set to be a random value from 10 to 40. The third algorithm was the great deluge, and the final algorithm was IDWalk. In the end, the algorithms were all compared. The lowest penalty on average was created by tabu search with a fixed tenure. The lowest penalty overall was found with the Great Deluge algorithm. It performed the worst on average but also was able to produce the best overall result. We have provided a table of the results to compare the different algorithms in

Table 2. Comparative Results.

Algorithm	Penalty Min	Penalty Mean	Penalty Max	Range
Tabu Search (fixed)	1270 (5)	1425	1520	250
Tabu Search (random)	1235	1342	1495	260
Great Deluge	1135	1720	3620	2485
ID Walk	1160	1391	1810	650

.

4.2. Physician/Emergency Room Scheduling

The next kind of schedule that is common in Canadian papers is physician scheduling in emergency rooms. This type of rostering falls under type one and is very similar to nurse scheduling. The two types of scheduling typically contain the same constraints and considerations with a few important distinctions. For example, physician shifts usually need to be filled by only one physician, but nursing shifts need to be filled by several nurses [17]. Another notable difference is the amount of work and stress that they undertake. This specific distinction in scheduling is important, as almost a quarter of ER’s in Canada are unsatisfied with their job, and a notable portion of this is directly related to scheduling woes. This affects patients as well, as over 44% of patients waited over five hours on their last emergency visit in Quebec, 2016 [31]. The other main difference is that arrival rates in the ER are random, so being able to predict them would change how the roster is made. Many schedules are still done by hand and can take a day or more to complete, so any improvements done will have a direct and palpable impact [16]. All of this culminates in a vibrant field with a large degree of innovation. A summary of each papers contributions is seen in

Table 3. Physician/Emergency Room Scheduling.

Paper	Methodology	Data
Beaulieu et al., 2000 [14]	Multi-objective IP, Branch and Bound	Sacré-Cœur Hospital in Montreal
Carter et al., 2002 [1]	Cyclic Mathematical Programming, Tabu search	Montreal-based hospitals
Rousseau, Gendreau, and Pesant 2002 [16]	Constraint programming, Local Search, Genetic Algorithm	Santa Cabrini Hospital, Côte-des-Neiges Geriatric Hospital
Gendreau et al., 2007 [17]	Constraint programming, Column Generation, Tabu Search, Mathematical Programming	Jewish General Hospital, Charles-Lemoyne Hospital, Santa-Cabrinwe Hospital, Sacré-Cœur Hospital, Côte-des-Neiges Hospital
Savage et al., 2015 [24]	Mixed integer programming, Poisson Generalized Additive Model	Thunder Bay Regional Health Sciences Centre
Camiat et al., 2019 [31]	Mixed integer programming	Sacré-Cœur Hospital in Montreal
Drysdale, Singh, and Goldenberg 2020 [23]	Gaussian Process Regressions	The Hospital for Sick Children, Toronto
Tohidi et al., 2021 [32]	MIP, Column Generation	Ambulatory Cancer Treatment Polyclinic in Montreal

. Some considerations that fall in this category are as follows.

4.2.1. Constraints

• Supply and Demand Constraints

  -

  Every shift must be assigned a physician [14].

  -

  During the overall planning period, every shift must be performed by exactly one physician [17].

• Workload/Availability Constraints

  -

  A physician cannot work more than one shift per day [14].

  -

  An evening shift can not precede a day shift [14].

  -

  Night shift cannot be assigned alongside another shift [14].

  -

  Vacations must be allowed and allotted [14].

  -

  Preassignments, forbidden assignments, vacations, preferences should be accounted for [17].

  -

  Limits on workload [17].

  -

  Limits on the number of shifts of the same type [17].

• Distribution Constraints

  -

  Physicians should work X hours a week [14].

  -

  Different types of shifts should be fairly distributed amongst staff [14].

  -

  Antagonistic shifts (day vs. night) should be fairly distributed amongst staff [14].

  -

  Distribution of types of shifts [17].

• Ergonomic Constraints

  -

  A limit on the number of shifts of a kind [14].

  -

  A limit to successive workdays [14].

  -

  A limit to the number of consecutive weekend shifts [14].

  -

  A weekend shift cannot precede a Monday shift [14].

  -

  Night shifts are recommended in groups of three consecutive shifts [14].

  -

  A day shift followed by a day shift must then be followed by two days off before another day shift [14].

  -

  Three consecutive night shifts should be followed by three days off [14].

  -

  Length of work sequences [17].

  -

  Patterns of shifts [17].

  -

  Patterns of sequences of shifts [17].

  -

  Patterns of sequences of a given length [17].

4.2.2. Papers

Beaulieu et al. [14] gives the first example of a mathematical programming model for scheduling physicians to the emergency room. They start by defining hard and soft (or, as they call them, compulsory and flexible) rules. Compulsory rules must be enforced for a solution to be feasible. Flexible rules can occasionally be unfulfilled, but they will incur a penalty. They then define demand rules, ergonomic rules, and distribution rules, as above, with the latter two being subcategories of flexible rules. There are a lot of constraints that go into scheduling a physician, and they are listed in the global constraint table.

This model is quite large and expressive, with approximately 40 thousand variables and 75,000 constraints. As such, solving for optimality is infeasible in the time frame that schedules would need to be created. Additionally, much of the conflict comes from the ergonomic rules, which are complicated and hard to compute. To find a solution, the rules that are most often violated are removed. From this point, a solution is produced, and the removed constraints are measured against it. Constraints that were removed and are violated are added back into the model, and a branch and bound algorithm is employed to produce the next solution. This is repeated until a satisfactory solution is created. Using a case study of Sacré-Cœur Hospital of Montreal which Beaulieu et al. [14] believe to be representative of the general population of hospitals in Ontario, not only was a notably better solution produced due to the large number of rules that are considered but was also magnitudes of order faster to produce. When done by hand such a schedule would take several weeks. This is a big selling point when most rosters are still completed by hand in Canada using a spreadsheet.

Rousseau, Gendreau, and Pesant [16] approach the problem by attempting to generalize physician scheduling so that it can be adapted in any hospital setting. They saw the work that was done but noticed that all attempts were either inflexible in the model of the algorithm. To improve upon this, they set out to make a constraint programming model that was generic and had programmable constraints. To begin, they define generic rules that can be used to adapt to different hospitals. The first generic constraint is the distribution constraint. It controls which physicians work which shifts relative to the days. The second generic constraint is the pattern constraint. This allows the author to define illegal states such as allotting an arbitrary amount of time between shifts. The model takes in all of these constraints and attempts to minimize the error. Again, with the generic aspects of this model, it becomes very difficult to solve to optimality. The solution they came up with is to solve the constraint program with a depth-first search on a branch and bound to get an initial solution, followed by a genetic algorithm to improve upon the answer. The constraint programming model is solved repeatedly to get a pool of candidate solutions, and this candidate pool is fed into the evolutionary process to iteratively improve them.

Their model was successfully applied twice in two separate hospitals. The first was the Santa Cabrini Hospital emergency room in Montreal, and the second was Côte-des-Neiges Geriatric Hospital. The conclusion is that while this approach does not benefit the end roster in any meaningful way, it does allow model flexibility. This offers the ability for other hospitals to adapt and utilize these techniques without starting from the ground up. The two case studies were replicated by taking previously created models and adapting them to the situation. The first case study was redone using an adaptation of the model by Beaulieu et al. [14]. It took significant effort to adapt as the model was not flexible enough to allow the constraints. The second case study was replicated using a Constraint programming model by Trilling, as cited by Rousseau, Gendreau, and Pesant [16], while it was able to create satisfactory solutions it was too intertwined with the problem as therefore was model inflexible.

A third look at the physician scheduling problem comes from Gendreau et al. [17] in the paper “Physician Scheduling in Emergency Rooms”. They attempt to provide a general overview of the problem, defining constraints that should be considered and comparing and contrasting different models. The constraints are the main contribution to the paper. The incentive to address this problem comes from looking into practical cases at a series of Montreal-based Hospitals. The commonalities between them helped define the rules that should be considered when creating a roster. Almost a quarter of all physicians are dissatisfied with their job, and working to create better schedules is a place to start that is proven to be effective. The types of constraint distinctions are the same as stated above. To solve this schedule, they contrast and compare four different models: a mathematical programming model, a column generation model, a tabu search model, and a constraint programming model. For each of these models, they overview where they have been utilized and a general overview of how it works.

Carter et al. [1] bring a fourth look into physician scheduling with the paper “Scheduling Emergency Room Physicians”. The same techniques and general constraints as covered prior are used to create their model. The data and ideas come from a survey of six major hospitals from Montreal. They also bring back the idea of cyclic schedules and create three different versions of the model: one acyclic, one cyclic with rotation, and one cyclic without rotation. To evaluate their approach to building models, they look into two different hospitals and compare their model results to those that are currently being used.

The first hospital they observe is the Charles-Lemoyne Hospital (CLH). Within this hospital is the second busiest ER within Quebec. CLH currently uses a cyclic schedule without rotation over a planning period of 37 days, which results in a simple model. Few constraints are considered when creating the schedule, including vacation days. Despite this, most physicians like the schedule, as it is fair, predictable, and easy to remember. The main gripe people have expressed with it is that weekends are often divided between work shifts and off days. If a new schedule is to improve on the current methodology, it should keep what physicians like about the current schedule while fixing what they do not. Using tabu search, better schedules were found that managed to tick all the boxes. The best schedule was later implemented, and most physicians were pleased with the changes.

The second hospital considered is Jewish General Hospital (JGH). JGH worked with acyclic schedules, and shifts were scheduled based on experience and teaching duty. This is a far more complicated system than the previous one. The drive to change the scheduling at this hospital stems from the amount of time it took to create. Around 40 h were devoted to preparing a schedule for three months. The physicians did like the schedules that were created, however. The authors were able to make a scheduler that could not only fulfill the requirements that were needed but could also consider physician’s personal accounts.

The other benefit that is offered to these two hospitals is the ability to fine-tune and change parameters at will. Allowing the model to be computerized permits them to make changes with a smaller amount of manpower and financial cost.

Camiat et al. [31] decide to take physician scheduling a step further by implementing a productivity-driven schedule. Emergency rooms are extremely overcrowded in Canada, and those in Quebec are alleged to be the worst nationally. They define productivity with two metrics: the number of patients seen every hour, and a relative time unit. The former is a ratio of patients seen, and the latter is an estimate of effort and practice expense. To address this, schedules created with physician productivity in mind could help alleviate some of the stress on the system.

They start to approach the problem by analyzing patient arrival times and then trying to use this information to predict how much stress there will be on the system at a later date. Data was used from the Sacré-Cœur Hospital of Montreal, which is a health center affiliated with the University of Montreal. Data from March 2008 to September 2017 was collected and analyzed containing approximately 600 thousand instances. This hospital employs 35 physicians and sees approximately 62 thousand patients per year. A decomposable time series model with the components growth, seasonality, and holidays was used to predict the number of patients that would arrive. It measured the number of patients that a physician was able to treat during their shifts. This index changes based on a multitude of variables, such as the day of the week and the type of shift. Using this data they can create demand forecasts. Following this, they introduce a measure of productivity called a productivity index, and use this to determine which physicians should be scheduled where. Using this index, the mathematical model matches patient demand to productivity. Additionally, to help alleviate stress on physicians, the model attempts to minimize unfairness as to not overload shifts.

Four different scenarios were tested, each with different weightings. All four had a weight of ‘100’ for under-staffing, ensuring that it would be of the highest priority. Scenarios two and four consider over-covering and under-covering with a weight of ‘1’ while scenario three has a weight of ‘10’ and one does not consider it. Finally, scenario one and three have a weight of ‘10’ for physician dissatisfaction and unfairness while the rest have a weight of ‘1’. Of the four scenarios, scenario four was the most balanced and showed the most improvement. It produced a schedule with no understaffed shifts, very little difference in shift distribution, and an average of 2.97 unwanted shifts. The success of this model demonstrates the benefits of accounting for patient forecasting and the faults of current scheduling.

Tohidi et al. [32] researches a variant of physician scheduling: physician scheduling under uncertainty. In this case, uncertainty refers to stochastic patient treatment durations. If a patient goes over the allotted time it will affect all subsequent scheduled appointments and if a patient finishes early that is time that is effectively wasted. The authors propose a 2 stage planning framework to help reduce the amount of uncertainty and more effectively schedule physicians.

The first step of the planning framework is the clinic scheduling and capacity planning problem. This involves scheduling the number of physicians required and the number of operating rooms that will be needed for the patients. To solve this a linear programming formulation of the problem is constructed and a mixed integer linear programming model is created. The method of solving this model is a variation on column generation called implementor/adversary algorithm. Column generation breaks an MIP formulation into a master problem and several smaller subproblems. The master problem is a smaller subset of all of the variables. After the master problem is solved, a sub problem is created with a variable thought to best improve the solution. The implementor/adversary algorithm treats the subproblems as adversaries until an optimal solution is found.

The second stage is the typical physician scheduling problem. This involves slotting physicians into the corresponding timeslots. To solve this they implement another MIP model. In addition, they create a sample average approximation algorithm in order to predict a patients duration within the clinic. This helps minimize the amount of time spent wasted or in overtime.

To validate their findings they worked in collaboration with an ambulatory cancer treatment polyclinic in Montreal, in which they were able to greatly lower costs and improve schedules compared to what was in use prior. Additionally, they believe that their model is generic enough to be implemented in many different clinics.

Physician scheduling papers also have a focus on attempting to optimize aspects of the schedule that are not the schedule itself. The probabilistic nature of the emergency room means that being able to predict aspects such as the number of patients, the downtime of the ER, the probability of an emergency, and other variables can allow for more flexible and efficient schedules.

The number of patients coming into a department is an unknown that can be optimized. Again, with the onset of COVID-19, capacities have decreased, and knowing how many patients are expected allows the schedule to better accommodate them. Drysdale, Singh, and Goldenberg [23] compared the results from The Hospital for Sick Children in Toronto from 1 June 2018 to 30 August 2020 to analyze how many patients visited the emergency department. The machine learning model used the Gaussian Process Regression (GPR) algorithm and trained on this data, making a prediction every hour and retraining every midnight. It was found that the model was able to achieve an average recall of 50–75% at predicting exact change, and 80% for any positive change. The sensitivity of the model could land anywhere between 20 and 70%, determined based on how acceptable false positives were. This variation comes from the fact that the GPR model is a probabilistic model. Additionally, they tested it against an AR-Lasso model and found that GPR outperformed it on all metrics. In terms of scheduling, this allows the hospital to know how many physicians should be scheduled at any given time and also how many patients they will be able to fit in.

Another paper that approaches the problem of patient arrival prediction is “Developing Emergency Department Physician Shift Schedules Optimized to Meet Patient Demand” by Savage et al. [24]. Likewise to the previous paper by Drysdale, Singh, and Goldenberg [23] they used historical data from their regional hospital to try and find temporal patterns and use this information to make predictions. This time they got their data from the Thunder Bay Regional Health Sciences Centre (TBRHSC) ED. The data was analyzed by fitting a generalized additive model (GAM). It used a Poisson framework, as this distribution best represented the arrival of patients. Using this predictive model they then created a mixed-integer programming model that utilizes the data generated to determine shift start times. The schedule generated was compared with the current schedule, and the new version outperformed it by all measured metrics in all scenarios. When used in combination with adding an extra fast track physician, unmet patient demand was lowered by as much as 69%.

4.3. Operating Room Scheduling

Operating room scheduling is a combination of type one and type two schedule, and can have a focus on one or the other. This can also involve scheduling the patients and medical staff to each operating room in addition to scheduling which operating rooms are available and what they will be used for. It is a more specialized example of scheduling that involves scheduling a resource, in this case, the operating room, to be used by the hospital. In many cases, this involves trying to minimize downtime while maximizing the effectiveness of the resource. As this is a more specific case of appointment rostering, many papers regarding this focus largely on ideas and algorithms that can be used to improve and evaluate the schedules rather than on algorithms that design and production schedules. The latter is covered more thoroughly by outpatient scheduling. Operating room scheduling must deal with many of the same considerations as outpatient rostering, such as rescheduling, cancellations, and maximizing the efficiency of a resource that deals with stochastic and online variables. Additionally, they are subject to unique pressures. The Canadian government has put a focus on reducing wait times and this has led to increased surgical volumes and bed utilization, which in turn lead to cancellations and wait times [33]. Operating rooms are especially valuable as they are one of the most profitable areas. About 42% of a hospital’s profit originates from the operating rooms while only accounting for 9% to 10% of the budget [2]. Other typical constraints are listed in Section 4.3.1.

The contributions of each paper are summarized in

Table 4. Operating Room Scheduling.

Paper	Methodology	Data
Santibáñez, Begen, and Atkins 2007 [34]	Mixed Integer Programming	Fraser Health Authority
Chow et al., 2011 [33]	Mixed Integer Programming, Monte Carlo Simulation	Royal Jubilee Hospital
Azari-Rad et al., 2013 [26]	Discrete Event Simulation	Toronto General Hospital
Saremi et al., 2013 [35]	Simulation Based Tabu Search, IP, BP	A Major Canadian hospital
Saremi et al., 2015 [36]	Multi-Agent Tabu Search, Mathematical Programming, Simulation	A Major Canadian hospital
Wang et al., 2016 [37]	Mixed Integer Programming, Discrete Event Simulation	University Health Network
Roshanaei et al., 2017 [2]	MIP, Bender’s Decomposition	University Health Network
Roshanaei et al., 2017 [38]	MIP, Bender’s Decomposition	Toronto General Hospital, Toronto Western Hospital, and Princess Margaret Cancer Centre
Diamant, Milner, and Quereshy 2018 [39]	MIP, Column Generation, Lagrangian Constraints, Integrality	Bariatric surgery Department in Toronto Western Hospital
Rozario and Rozario 2020 [25]	Machine Learning	Oakville Trafalgar Memorial Hospital
Wang et al., 2020 [40]	Time Series Analysis, Statistical Analysis	Ontario based administrative data sources
Oliveira et al., 2020 [41]	Mixed Integer Linear Programming	Hospital in Quebec City
Roshanaei et al., 2020 [42]	MIP, Bender’s Decomposition	University Health Network
Naderi et al., 2021 [21]	Mixed Integer Programming, Benders Decomposition, Constraint Programming	Toronto General Hospital
Guo et al. [43]	Mixed Integer Programming, Benders Decomposition	N/A

.

4.3.1. Constraints

With all of the considerations an operating room has the constraints tend to not be divisible into neat categories as the previous types of schedules. There are sometimes multiple different schedules being created in tandem and this leads to more broad constraints.

• Patients with a high priority must be scheduled within the planning period [2,37].
• If additional space is available non-priority patients can fill it [2].
• Doctor’s should be allowed to set a preference regarding the type of patients they see [41].
• Each surgeon can only work at one hospital [2].
• Total surgical time does not exceed total OR time [2,34,37].
• Each OR is assigned to one specialty [34].
• Each OR must have the same specialty every week [34].
• No specialty can be over-represented [34].
• Surgeries can only be performed in the appropriate OR with the appropriate specialty [2,34,41].
• Patient throughput must meet a specified threshold [34].
• Beds should be minimized [34].
• Operating rooms and specialties must be compatible in aspects such as equipment and specialty requirements [34].
• Time must be allotted for patient recovery [34].
• Overtime should be avoided if at all possible [41].
• Surgeries cannot go over the predicted time based on surgeon skill and standard duration [41].

4.3.2. Papers

A first look at scheduling operating rooms comes from “Surgical block scheduling in a system of hospitals: an application to resource and waitlist management in a British Columbia health authority” by Santibáñez, Begen, and Atkins [34]. Operating room scheduling differs from previous scheduling methods, as there are more variables to consider. Different specialties require different setups in the operating room, so they need to be scheduled differently. Factors such as wait time, capacity, and priority now need to be considered. In tackling this problem, Santibáñez, Begen, and Atkins [34] define three stages of scheduling for this purpose. The first stage determines the amount of time each specialty should be allotted. The second stage divides the OR specialties up on a per-day basis, creating the schedule itself. This process is called the surgical block scheduler. The third stage schedules the individual patients. This paper focuses on how to construct the second stage. The first stage is assumed to be completed, and so creates a list of constraints that need to be followed. The schedule, created for the Frasier Health Authority, must follow the constraints given and must also be cyclic: able to be applied every week. The model created was a mixed-integer programming model and was solved for optimality the majority of the time. Data was analyzed from eight hospitals, with each one covering 4000 to 11,000 cases and from 3500 operating minutes to 15,000 operating minutes. From here, four main scenarios were analyzed and are summarised in

Table 5. Outpatient Scheduling Papers.

Scenario	Description	Results
Present State Analysis	Evaluates model’s accuracy and current status	Returned the maximum number of beds utilized.
Resource Optimization	Identifies schedules with a smaller number of beds and lower bed utilization fluctuations	When optimizing for bed usage, the model was able to require  39 fewer ward beds and a similar number of special care unit (SCU) beds.
Waitlist Management	Determines how many resources are required to stabilize waitlists	When optimizing for waitlists the bed usage still decreased, this time by about four beds.
System-Wide Analysis	Studies benefits of hospitals that collaborate	When using collaborative methods between hospitals, further bed reduction was possible.

.

Overall, by focusing on optimizing the surgical block scheduler, it was possible to increase the throughput of patients while decreasing resource utilization. On average the model was able to reduce the number of ward beds by an average of 4.85 and the number of special care unit (SCU) beds by 0.05.

Chow et al. [33] offer a second look at creating a surgical block scheduler. They propose the following surgical scheduling framework: A surgical schedule optimizer (SSO) and scheduling guidelines are the input into the framework. This input is then sent to a bed utilization simulator (BUS) and the output is evaluated. The input is then updated with the output until a final surgical block schedule is generated.

The framework consists of two models: an SSO to create the schedule, and a BUS is used to evaluate the schedule that was created. Now that schedules contain more stochastic elements, evaluating them goes beyond just satisfying constraints, and simulations must be run to determine their effectiveness. Starting with the BUS, which predicts ward bed’s daily demand given an uncapacitated system, planned patients are predicted to arrive based on historical data and are then classified into patient types. Unplanned patients are generated using a Poisson distribution. These patients are then sampled to create ward occupancy patterns. The schedule is evaluated using the metric “bed-days over capacity”, which is a measure of the number of extra beds and allows an estimate of patient off-servicing or surgery cancellation. The SSO used data from the BUS as well as surgical guidelines to create a schedule that optimizes bed occupancy. The SSO contained two models: a base model which assigns surgical blocks, and a slate model, which in addition to assigning surgical models also determines patient type mix within a given block. Both models are mixed-integer programming models.

To fully evaluate this framework, a case study was done on the Royal Jubilee Hospital (RJH) in Victoria BC. This hospital is the main hospital for over 350 thousand residents, has 16 operating rooms, and 42 inpatient beds. Using both the BUS and the SSO led to a 16% reduction in bed days over capacity. This means 13 cancellations or improper wards could have been avoided. When using the slate mode, an increase of 15 surgical cases was reported. This left to bed-days over capacity being reduced by 9% and surgical volume increasing by 5%. The model was able to produce this result in about 10 min, however, if optimality was desired it would take over six hours. The difference between the suitable solution and optimality was within 1%.

Guo et al. [43] do not work with a specific hospital but do review others that work with Canadian hospitals as well as justify their work with Canadian statistics. They look to solve the stochastic distributed delivery room problem. They first motivate their work with the statistic that 30% of patients who need hip replacements and other similar surgeries wait longer than the recommended wait time in Canada. This obviously can lead to detrimental outcomes on the patient as well as the staff. By producing better schedules they aim to improve this area of healthcare and allow better access to vital surgeries. They model their program as a 2SIP (2-stage stochastic integer program) problem. As the problem is stochastic they first generate random scenarios to represent the length of each surgery. They solve the problem approximately based on each random vector and find an expected cancellation cost by averaging the results.

With this information they are able to begin solving the problem more optimally with decomposition methods. The first stage of their methodology is to find an initial solution using a process called first fit decreasing. This allows the solver to start with a warm start. Stage 2 involves solving the problem with an ILP solver. As the problem is quite complex they introduce both logic based Benders cuts and binary decision diagram cuts to help reduce the problems size. They also include classical Benders cuts. As an alternative, they also introduce a three stage framework to solve more complex instances of the problem in which the subproblems are further sub divided into 2 stages. Their scheduling framework was able to find more robust schedules and allow more patients to be seen in simulated trials. Guo et al. [43] provides both comparisons to CPLEX as well as sensitivity analysis to validate the efficacy of their algorithms.

Diamant, Milner, and Quereshy [39] investigate outpatient scheduling in a multidisciplinary, multistage process. The current methodology in the Bariatric surgery Department in Toronto Western Hospital involves scheduling patients for a single assessment on a later date. Appointments and assessments are scheduled at the same time, upon completion of the last. This leads to a system which is not robust against cancellations and changes, as well as not efficiently using resources. Diamant, Milner, and Quereshy [39] propose a new methodology that schedules patients in an offline fashion at the start of the day, sometimes over multiple timeslots to increase robustness. There model is based on mixed integer linear programming and offer multiple different avenues to solve the problem. They first aggregate constraints into single constraints to reduce the dimensionality of the problem and solve using integrality, lagrangian constraints, and column generation. We observe that the best model presented has an average or utilization in of 90% in most instances and increases average clinic profit should it be implemented. The allowance of multiple assessments allows the clinic to be more flexible and adaptive when it comes to appointments and can drastically increase staff output.

Roshanaei et al. [2] offer a collaborative look into operating room scheduling. Instead of scheduling just one hospital, they attempt to improve the schedule by having the hospitals work in tandem to produce the best global solution. Their model is a mixed-integer programming model. Introducing collaboration also introduces hundreds of new constraints and variables, so solving the model, even suboptimally, becomes a computational problem. To address this, Roshanaei et al. [2] use a technique called Benders decomposition, formulated by Bender in 1962 [44]. Similar to column generation, it involves decomposing a problem into subproblems, which are easier computationally. To evaluate their model they used data from University Health Network hospitals, including the Toronto General Hospital, the Toronto Western Hospital, and the Princess Margret Cancer Centre. By collaborating with dedicated patients, a cost savings of 6.08% was achievable. Including flexible and semi-flexible patients increased the savings to 26.37% and 39.89%. Collaborative scheduling also increased throughput, leading to 9.25% higher patient admission. To further prove that a collaborative network of operating rooms more effective, a game theory lens is used to look at the results. By measuring the average contribution of each hospital a payoff value is computed. It was found that joining the collaborative network was in each hospital’s favour, as it led to a higher payoff. Overall, when hospitals chose to share resources it was a net benefit for all of them at the cost of computational complexity.

In addition, Roshanaei et al. [42] introduce several techniques for creating balanced operating room schedules based on ILP. The balanced distributed operating room problem again attempts to schedule multiple hospitals collaboratively to better improve patient output and care. They begin by extending the non balanced distributed operating room ILP to include both macro and micro balancing objective functions. Micro imbalance ensures that shifts are distributed evenly within each individual hospital while macro imbalance ensures that each hospital is treated equally. Two different objective formulations are given for micro imbalance: one linear and one quadratic. Macro imbalance is always treated linearly. Furthermore, Roshanaei et al. [42] provide linearization techniques and decomposition techniques to further optimize their models. In the end, three models are presented. One mixed-integer quadratically constrained program and two mixed integer constrained programs. The models are then solved using both uni-level and bi-level logic-based bender’s decomposition.

The three models were validated using three collaborating hospitals in the Toronto area: Toronto General Hospital, Toronto Western Hospital, and Princess Margaret Cancer Centre. Test cases solved via Gurobi found that MIP models were able to solve within 2% optimality within 30 min.

A third view on distributed operating room scheduling comes from Roshanaei et al. [38]. With another novel iteration on logic-based bender’s decomposition and cut propagation. Here, they introduce 3 approaches to solve large scale problems. To generate the probability distributions the authors utilized data from the General Surgery Departments of the University Health Network in Toronto. Their methodology was significantly faster than using conventional solvers and were also able to handle problems of a larger scale.

Oliveira et al. [41] explore integrating patient priority into scheduling in hopes that it improves access to operating rooms. To do this, each patient is assigned a utility score, which represents their priority and urgency. The integer linear programming model is then directed to maximize this utility. The model was built with the considerations of the University Health Centre, Quebec City.

Before implementing the model in its totality they wanted to demonstrate its efficacy and determine how much it would help the hospital. Firstly they generated dummy data to simulate patient data. A second, simpler model was created that instead of trying to maximize utility it instead maximized the number of sessions such that the longest wait times were scheduled first. This new second model would act as the control and allow comparisons between the two approaches. Four metrics were measured for both models and are summarised in

Table 6. Comparative Results.

Model	Utility	# Sessions	# Surgeries	Max Surgeries
Utility Model	69.83/58.06	15.16/19.65	116.7	4.4
Longest Wait Model	64.10/65.96	17.93/15.80	111.7	4.3

. The first metric is the average utility of both the scheduled and unscheduled patients. The second is the number of sessions that each scheduled and unscheduled patient waited. The third is the number of surgeries the OR was able to perform. Finally, the last is the largest number of surgeries scheduled to a doctor.

This results in positive results in favour of utility prioritization. The utility model not only allowed more patients through the system, but the patients that went through would be more urgent. The wait times for the unscheduled patients do get increased compared to the other model however and this could result in deadlock or unnecessarily long waiting times for low priority patients. Despite the efficacy of the utility model, Oliveira et al. [41] suggest additional research into the idea before it is implemented. This research could be done in terms of improving the model computationally to allow for optimal solutions, and also test against different distributions of patients to ensure it works as intended.

Naderi et al. [21] focus on the general problem of generalized OR planning and scheduling (GORPS). As of the writing of this paper, COVID-19 was still ongoing and putting strain on the hospital system and putting pressure on the number of available beds. This was one of the inciting forces in researching this problem. GORPS involves optimizing the act of scheduling patients to each day, members of resources to each timeslot, members of resources to patients, and creating a surgical scheduling block. To solve this problem they create a mixed-integer programming model using four different paradigms to compare and contrast how each performs. The four paradigms are sequence-based, immediate sequence-based, position-based, and time-based. A sequence-based model focuses on surgery pairs that can be assigned to a member. This version does not assume that the precedence between the pair is immediate. Essentially it attempts to come up with the most optimal ordered list of schedules. Immediate sequence-based scheduling does assume that the precedence is immediate. Position-based scheduling is where each patient is allotted one position in a list of resources, however, multiple resources can occupy the same position. This is the most common paradigm used in papers featured here and it was first introduced in this paper by Rosenbloom and Goertzen [19]. Time-based is the a growing paradigm that is more popular in more recent papers. It involves taking each time parameter (day, shift, time period) and discretizing them. After each surgery would be allotted a time slot. These four paradigms offer four different approaches to encoding the data and building the model. A fifth constraint programming model is introduced as well, while harder to solve for optimality, it is more than capable of returning a satisfactory solution. Another improvement that is made is assuming that overtime is a discrete variable as opposed to a continuous variable. This heavily punishes going over specific thresholds. Likewise to Roshanaei et al. [2], Naderi et al. [21] implement Bender’s decomposition to reduce the scope of the problem and to explore other options, such as Branch and Check to compare decomposition methodologies.

Naderi et al. [21] use data gathered from the General Surgery Department of the Toronto General Hospital (TGH). It spans July 2011 through June 2013 and contained 2711 surgeries. The best model was able to receive an optimality gap of 24.69% while the constraint program does considerably worse with an average optimality gap of 70.37%. Using logic-based Benders decomposition the average optimality gap was reduced to 2.71%. It was found that the constraint programming model was inefficient in comparison to linear programming models, even when computing subproblems. The paper concludes with insights into how TGH should react given this information. COVID-19 has resulted in a large backlog of cancelled surgeries due to the restrictions placed on elective visits. To account for these new patients, the models are rerun with additional instances of patients and this gives insight into how many additional patients the current resources can handle. It was concluded that the bottleneck was not the number of operating rooms but rather downstream resources such as ICU beds which prevented increases in patients. Investment into this area could dramatically increase revenue and throughput. Future work could be done to implement stochastic processes such as simulating patient arrivals or to further improve upon computational aspects of the models.

Saremi et al. [36] look into the issues that are presented by appointment scheduling with heterogeneous service sequences. First, they assume that patients can be scheduled to do many different sequences. Some may show up for a checkup, while others may have surgery. The scheduling is done using a mathematical programming model. To incorporate the stochastic elements, they use discrete event simulation (DES) modelling. The simulation is a lognormal distribution that determines aspects such as the number of patients or open ORs. After a pool of initial solutions is generated, it is then solved using a multi-agent tabu search that attempts to optimize waiting and completion time. With two variables to consider, there is an infinite number of “optimal” solutions that lay on a Pareto front. The model iterates through the tabu search, trying to converge on the Pareto front. Their model was compared against NSGA-II, a popular genetic algorithm on the metrics of closeness to the Pareto frontier and smoothness of distribution. The new model performed better on both cases and additionally had less computation time.

In addition to the model creation, a case study was done in a large Canadian hospital which houses approximately 500 beds, 10 ORs, and performs 8000 surgeries every year. Their methodology was able to offer solutions that were equal to, if not better than, the ones used previously. It also allowed more flexibility, as aspects such as overtime, cost, completion time, and more could be optimized for. This procedure offered some insight into how schedules should be created in the future. Overtime should be minimized at all costs, as it leads to fewer mistakes and decreases financial cost. Longer appointments should be scheduled early or in the middle of the day as they are the most variable, and scheduling them later in the day can lead to overtime. Surgeons should be in the same room as this will limit turnaround time. The least flexible appointments should be scheduled first, so if flexibility is needed the more flexible appointments can bear it. Finally, similar cases should be scheduled in the same OR to maximize throughput.

Saremi et al. [35] look at a very similar problem, but with a different methodology. They also attempt to solve the problem of operating room appointment scheduling while optimizing wait time and completion time, and consider the number of cancellations. This time they propose three models, all of which are simulation-based tabu searches. The first is technique is simulation tabu search (SBS). This starts with an arbitrary solution not generated by a mathematical programming model. It is then further iterated upon by using both an integer programming model and a binary programming model to generate the initial candidate solutions. The simulation model is a discrete event model that outputs the stochastic elements such as how many patients arrive and of what type. The simulation runs for 30 replications and returns the results. The initial model, which used an arbitrary starting solution, performed worse than the other two and was mainly used as a stepping stone to define the others. Both the integer and binary versions produced similar solutions, but the integer version was much slower. An integer solution is much more restrictive than a binary one, so the Binary Programming Enhanced tabu search (BPETS) was recommended for practicality. After creating the model, a case study was run using BPETS at an important hospital in Canada. This led to a large reduction in completion times in their OR department.

Wang et al. [37] offer a final look into building an operating room scheduler in the paper “A discrete event simulation evaluation of distributed operating room scheduling”. This paper utilizes a deterministic integer model called DORS for scheduling patients. The model is then evaluated using a discrete event simulation (DES) modelling. The DES model was built using data from the University Health Network which includes Toronto General Hospital (TGH), Toronto Western Hospital (TWH), and Princess Margaret Cancer Center (PMCC). The model contains three main parts: the patient arrivals, the ORs, and the downstream units. Patients arrive and are waitlisted each day. At midnight they are scheduled one by one by priority, or until OR capacity is reached. Like previous papers, there are two main categories of patients to arrive: elective or expected patients, and emergency patients, which are random. After being scheduled, a patient will go into a queue and wait to enter the OR before being routed through downstream units. For an optimization model they utilize the one by Roshanaei et al. [38]. When creating the model, three main situations needed to be handled: cancellations, emergency patient handling, and the warm-up period. To evaluate the DES, the following metrics were used: throughput, OR utilization, overtime, cancellations, and cost. Patient data was collected from January to June 2013. Evaluating the model and DES on TWH, the OR days needed for elective patients were decreased by 16.6%. The cost of this was slightly lower throughput in both emergency and elective patients. Using the new models, OR utilization was also increased by 49.9% to 63%. The model even managed to bring a 5.4% reduction in cost, and a 1.9% reduction in per surgery cost. Many other metrics were also considered. To study the effects each parameter has on the output an ablation style study was conducted. By ignoring the variable length of surgeries cancellations rose 2% and OR utilization dropped by 72.2%. Forgoing dynamic patient arrivals affected the aforementioned statistics by 5% and 67.1% respectively while limiting downstream resources had the effect of 23% and 50.6% respectively.

Many papers focus on optimizing aspects of schedule making rather than the schedule itself. Instead of building a model, Rozario and Rozario [25] as well as Azari-Rad et al. [26] try to optimize the estimations needed to make the models work.

One aspect of schedule creation when booking appointments is the length of the appointment. There are not always good ways to determine how long a patient will need to be seen. If you overbook you will have long wait times, and if you underbook you will have lots of downtime that could have been used to treat patients. Rozario and Rozario [25] address this in their paper “Can machine learning optimize the efficiency of the operating room in the era of COVID-19”. This problem has been especially exasperated in the last year, as many elective surgeries have been cancelled due to the emergence of the novel coronavirus. Due to this, the number of people who can get through is more impactful. They compare a machine learning model which predicted the length of scheduling times compared to using the mean scheduling time and learned that in doing so the operating room would have been in overtime 27% of the time compared to 48% of the time otherwise. Additionally, the undertime reduces from 37% to 18%. These data were collected from the Oakville Trafalgar Memorial Hospital in Ontario.

Azari-Rad et al. [26] used discrete event simulation (DES) and data from the Toronto General Hospital to see if surgical cancellations could be reduced. The longest cases should be scheduled first, as this limits the amount of overtime and prevents rescheduling or cancellations. The main problem is that many appointments are random, and cannot be known upfront. To address this, the model first creates a schedule and assigns timeslots based on factors such as which OR is available. The simulation then takes data from the historical records and simulates whether the patients can go through with their surgeries. They then studied three different scenarios to see how this would affect the frequency at which surgeries were cancelled. The first is to create schedules based on the length of stay of their patients. Surgeons who usually had a shorter length of stay were scheduled earlier in the week. The second scenario is scheduling surgical procedures based on surgery time and surgical time variation. The last scenario was simply adding more beds to the OR.

Creating schedules based on increasing length of stay consistently decreased surgery cancellations. Adding beds had the same effect. Additionally, ordering schedules from shortest to longest and from lowest variance to highest variance greatly outperformed the contrary.

Much like the papers by Savage et al. [24] and Drysdale, Singh, and Goldenberg [23], Wang et al. [40] look into how to use historical data to predict patient arrivals. Their work was spurred by the effects of the COVID-19 pandemic, which has created a severe backlog of patients whose surgeries were cancelled. The goal was to determine how many surgeries require scheduling and how many additional surgeries a operating room could handle in attempts to whittle down the list. The data was gathered from six different sources:

• The Province of Ontario Wait Times Information Systems.
• The Canadian Institute for Health Information National Ambulatory Care Reporting System.
• The Canadian Institute for Health Information Discharge Abstract Database.
• The CorHealth Ontario Cardiac Registry.
• The Trillium Gift of Life Network Organ and Tissue Allocation System.
• The Surgery Efficiency Target Program.

From these sources it was estimated that there were around approximately 148,364 surgeries in the backlog that needed to be scheduled. This estimate comes from the predicted vs. observed surgeries using historical data from 15 March to 13 June. As surgeries were cancelled this led to a drop in surgeries being performed and with this data we can extrapolate an approximate number of cancellations. The next step was to estimate how much additional stress the system can withstand given new surgeries. Time series models were used to forecast surgeries to determine both how long it would take to address the issues and what resources would be needed. Probabilistic sensitivity analysis was used to account for uncertainty. It was found that on average it would take 9 ICU beds, 265 ward beds, 719 OR hours every week for 84 weeks to eliminate the backlog. This would allow the operating rooms to allow an additional 717 patients through. The overall goal of this data collection is to pass it onto Regional Leads who in turn can use this data to more efficiently and effectively schedule ORs.

4.4. Outpatient Scheduling

Outpatient scheduling is different from staff scheduling and is a prime example of type two schedules. It introduces the problem of updating a continuous schedule as opposed to creating a schedule from scratch each time. It is impossible to predict if, and when, patients will arrive because they are random in nature, meaning it is much harder to verify optimality. Additionally, one must consider factors such as rescheduling, cancellations, overtime, and downtime. Due to this stochasticity, simulations are typically used to stress test a model and determine its effectiveness. Some common considerations regarding this kind of roster are as follows:

• Overtime should be capped at a maximum value [45].
• Each patient should be assigned a slot [45].
• Each timeslot should only be given one treatment [45].
• Overtime should be balanced between each nurse [45].
• Any patient can accept a timeslot [22].
• Multiple patients cannot occupy the same timeslot [22].

A summary of each papers contribution and where it was implemented is found in

Table 7. Outpatient Scheduling Papers.

Paper	Methodology	Data
Klassen and Yoogalingam 2009 [46]	Neural Network, Simulation, Search Heuristics, Tabu Search, Scatter Search	N/A
Godin and Wang 2010 [22]	Multi-Agent Iterative Scheduling, MIP	N/A
Hahn-Goldberg et al., 2014 [47]	MIP, Constraint Programming	Odette Cancer Centre in Toronto
Le et al., 2015 [45]	Greedy Algorithm, Tabu Search	Regional Hospital at Trois-Rivières
Ma et al., 2016 [48]	Discrete-Event Simulation, Mixed Integer Linear Programming	British Columbia Cancer Agency Regional Centre
Kandakoglu et al., 2020 [49]	Mixed Integer Linear Programming	Nephrology Division at The Ottawa Hospital
Benzaid, Lahrichi, and Rousseau 2020 [50]	Discrete-Event Simulation, Mixed Integer Linear Programming	Centre Hospitalier Universitaire de Montreal
Hooshangi-Tabriz et al., 2020 [51]	Multi-Objective IP, Weighted Sum Method	Segal Cancer Centre in Montreal

.

Papers

The most common area of outpatient scheduling is in the field of oncology and cancer research [45,47,48,50,51]. It is the leading cause of death in Canada with over 233,900 cases in 2021 and 85,100 deaths [52]. It is estimated 40% of Canadians will be diagnosed within their life. Efficient scheduling of cancer outpatients could improve mortality and allow more patients to be seen.

Le et al. [45] focus on the problem of appointment scheduling for chemotherapy. This type of schedule is unique as there are over 115 different types of treatments that can be done on a patient, each with its own duration, frequency, etc. To begin they build a mathematical programming model and gain their initial solution using a greedy algorithm. As patients come in they are added to the schedule wherever they fit. There are two ways they can do this: vertically and horizontally. Vertical scheduling is scheduling on a per-day basis and horizontal scheduling is scheduled on a per-period basis. To get a balanced initial solution a mixed treatment strategy is utilized which combines the two types of schedule additions. Following this, they attempt to solve the problem using tabu search. The tabu search will grade the solution based on the number of patients, the amount of overtime, and the nurse’s workload. They use four neighbourhoods during this phase. The first neighbourhood they consider is the Fitting Lunch-break neighbourhood. This neighbourhood states that patients cannot start their treatment while a nurse is on their lunch break. The second neighbourhood is the Intra-Day neighbourhood. It reorders the treatments to fill in the gaps left by the previous neighbourhood. The third neighbourhood is the Consecutive Days Exchange neighbourhood. This one swaps the treatments of the consecutive days with the largest difference in patients seen. Finally, there is the Non-consecutive Days Exchange neighbourhood. It swaps between any two days, but only within the first two weeks.

The model was designed to be used in the hematology-oncology clinic in the Regional Hospital at Trois-Rivières. Given the model, they were able to schedule all patients within three weeks as opposed to the four that had been done manually. Additionally, it produced a more balanced schedule, better dividing treatments within the week.

Another appointment scheduling paper comes from Ma et al. [48]. They address patients who need oncology appointments. Similar to Wang et al. [37], Ma et al. [48] build a discrete-event simulation framework to help study the impact of their optimization model. The actual optimization model is a mixed integer linear programming model. They then evaluated their model with data collected directly from the British Columbia Cancer Agency regional centre.

The process first begins with deriving data from the simulation. The simulation first considers tumor location and wait time tolerance. This determines how urgent a request is. Based on this information the request is then added to the schedule, diverted, or added as an add-on. It was found that first come first serve was the most impactful rule in place. No specialization rules could outperform this rule to a significant degree. The general conclusion in this paper is that the impact of scheduling software is most noticeable when capacity is close to the average level.

Furthermore, Benzaid, Lahrichi, and Rousseau [50] look into scheduling chemotherapy appointments with daily outpatient-nurse scheduling. This problem was presented by the Centre Hospitalier Universitaire de Montreal. A two-stage decision support system procedure is proposed. The first stage is further divided into two substages. In the first substage an appointment scheduling problem is solved. This assigns a timeslot to each outpatient. The second substage solves a staff planning problem to determine which staff is available for each patient. Once these have been solved stage 2 solves the daily patient-nurse assignment problem. This step is a dynamic step that allows constraints such as last minute changes or cancellations. The first stage has both substages modelled as a mixed integer linear programming model. The second stage utilizes a simulation model to predict cancellations and absences for the online model. The online model is a combination of an MIP model updated with the simulation data. The final insights reveal that modeling the waitlist and using optimization was able to improve productivity as well as improve throughput. They also discovered that overbooking the hospital to some degree would be beneficial as it offsets cancellations.

Following in the same vein, Hahn-Goldberg et al. [47] tackle chemotherapy outpatient scheduling with a case study based on the Odette Cancer Centre in Toronto. To solve this dynamic problem they break it into two steps. The first step is to solve the offline version of the problem using constraint programming. The second is to predict appointments and their features using statistical analysis. This allows the author’s model to incorporate features such as extended stays and cancellations. Testing their model on 30 instances representative of real world events, their model was able to improve on the current scheduling method used in practice of 15%, but was not able to reach optimal solutions in most cases.

A final look into cancer outpatient scheduling comes from Hooshangi-Tabriz et al. [51] in their paper “Improving Patient-Care Services at an Oncology Clinic Using a Flexible and Adaptive Scheduling Procedure”. Like similar papers prior, the authors propose a two stage model. The first stage is an online model which accepts and schedules incoming appointments. This model is a multi objective model which attempts to minimize the number of appointments in the waiting list, the number of appointments which are not in the preferred slot, the number of buffered requests, and nurse overtime. The seconds stage is a model which re-books existing appointments in hopes of further optimizing the schedule. The first stage models the problem as integer programming models. They use a weighted sum method in order to solve the instance and a technique called analytic hierarchy process to determine the importance of each objective. The second model is constructed in a similar manner.

They also include a third module which is called when unexpected events occur, such as cancellations or reschedules. This calls the second model in an attempt to reschedule around these events. This increases the robustness of the framework.

Hooshangi-Tabriz et al. [51] worked alongside the Segal Cancer Centre in Montreal to conduct their research. Their framework was able to outperform the current methodology accross all objectives and all instances.

Some papers have taken an entirely different approach to all of the others. “Agent-Based Outpatient Scheduling for Diagnostic Services” by Godin and Wang [22] is one of those papers. Godin and Wang [22] have set out to schedule outpatients, which is a dynamic process. Instead of modelling what a valid schedule is solely using a mathematical or constraint programming model, they have modelled the process as an agent-based system. They start by modelling the patient, the facilitator, and the diagnostic service as agents. These agents all have their own goals and send each other messages to achieve these goals communally. The process starts with the negotiation protocol. This protocol is where the timeslot is allocated to the patients. It starts with the DS agent acquiring and forwarding all available timeslots to the patients. If a patient is interested, it bids on a timeslot. Patients then wait as the schedule is updated, and the cycle repeats if patients either want to update their scheduled slot or still need one in the first place. This ends up being an iterative scheduling method that starts with a blank, or partially filled, schedule and slowly accumulates appointments. The DS agent’s local decision-making is where the programming model is contained. Its job is to determine timeslots that are available and ensure that they obey a set of constraints. This approach, if outpatients are willing participants, could allow for automated scheduling. The more important benefit is that this allows empty timeslots to be filled last minute. Many times, cancellations or rescheduling leaves vacant timeslots and downtime that goes unused, and this change provides willing participants with the opportunity to capitalize on that.

Klassen and Yoogalingam [46] in their paper “Improving Performance in Outpatient Appointment Services with a Simulation Optimization Approach” have the goal of trying to optimize their simulation. The simulation is designed to determine the optimal setup, given that the situation they are working on is not deterministic. They start their simulation by creating an initial, diverse set of candidate solutions. After they have been set, each candidate is run through the simulation a variable number of times decided by their neural network accelerator during the simulation phase of their model. It is used to learn how many replications to run. When simulating an event in a way such as this, you must ensure that the solution is stable and the neural network is there to help verify that it is. All new solutions are then passed onto an optimization algorithm. The optimization algorithm uses these solutions to evolve into the next series of solutions using scatter search and tabu search. Scatter search allows the mapping of an infeasible solution into a proper solution. This allows the information in the infeasible solution to be maintained. The scatter search is used to home in on the optimal solution, and the tabu search is there to ensure a variety of solutions are being considered. The simulation optimizer stops once a certain convergence has been achieved.

Klassen and Yoogalingam [46] tried several measures of schedule performance and found that depending on which was used, the results varied greatly. The five that were settled on were:

• Cost of client waiting time.
• Cost of waiting and server idle time.
• Cost of waiting and overtime.
• Cost of waiting, idle, and day end time.
• Cost of waiting, idle, and overtime.

One of their main priorities was using these metrics to determine now scheduling patterns. They found that the best schedules tended to have a constant distribution throughout and this was called the dome pattern. A dome pattern holds a value near constant for a majority of the range of the independent variable, causing the graph to visually display a rise, a plateau, and a fall.

By creating a constraint to represent the dome, they believed that it would serve as a useful pattern for scheduling. Adding in constraints to represent this pattern only reduced evaluations by 0.22% proving its legitimacy. To further test this pattern they experimented with patient no-shows and found that on average patient no-shows only led to a 0.19% drop in performance on average. It also faired well when given variable session length.

Kandakoglu et al. [49] focus on a different area of scheduling. They worked in tandem with the Nephrology Division at The Ottawa Hospital to schedule home dialysis machines for patients with kidney failure. Their contribution is a decision support system built upon a mixed integer programming model. The ILP creates the schedules which are passed onto the nurses to help inform their itineraries. Home dialysis scheduling offers unique challenges not present in any work discussed this far as it has to incorporate constraints such as travel time and distance. The decision support system incorporates breaks, overtime, cost, and lunches among other considerations. Their model was tested and evaluated using data supplied from The Ottawa Hospital and it was found to improve work distributions and minimize cost, and distance.

5. Overview

Most papers can be broken down into three components. The construction of the mathematical model, the construction of a solving algorithm, and a results section to verify the efficacy of the solver.

When it comes to constructing a mathematical model, physician scheduling goes the most in-depth with nurse scheduling a close second. They have the most unique constraints and explore additional parameters such as nurse fairness and relative priority between different staff members. Outpatient and OR room scheduling explore far fewer constraints, leading to less variation between each model. Nurse and physician scheduling solvers are also more likely to be modular and generic, furthering the likelihood of compatibility within various hospitals. Both physician and operating room scheduling had instances of online and static scheduling, while nurse scheduling was solely static and outpatient was solely dynamic. With combinations missing, future work may be done. Figure 3 shows the choices made.

The choice of model also helps determine which direction improvements may be done. With static instances, the research tends to explore improving the solvers for the models. Dynamic instances have more choices, often creating simulation models or constructing algorithms to predict probability distributions.

A pattern worth noting is that exact methods have completely dominated the market in recent years. From 2016 on-wards no paper focuses on a metaheuristic, opting instead for integer linear programming with column generation or bender’s decomposition. This method can be aborted early to get approximate solutions. This may be in part to long schedule creation periods and improvements in linear programming, however, with different requirements across the domain it is difficult to give exact reasoning. Of those that did include both exact and methods such as Gendreau et al. [17] Rousseau, Gendreau and Pesant [16], comparison and sensitivity analysis were minimal. Figure 4 shows some choices that may be made when choosing between which solving algorithm to utilize. Within the papers that do explore heuristics, the selection of heuristics chosen is very limited. Three major heuristics in Tabu search, local search, and genetic algorithms are chosen. Further exploration into additional heuristics may be warranted.

While results have been nearly universally positive, direct comparison between different studies is difficult. Each paper provides a different problem to solve and few papers offer statistical analysis or comparison between different models. This results in a situation where improvement as a field is hard to quantify. Better evaluation within all domains would help. Comparisons between different solving methodologies or comparisons of schedules over significant periods would serve to better prove which methods are effective. Figure 5 contains ways to evaluate your model and solver to better represent its effectiveness.

By improving these three aspects of scheduling better timetables will be created.

6. Tools

With so many different approaches to the scheduling problem, it would stand to reason that the algorithms being used will be varied as well. A majority of papers provided a concrete implementation of the model. Each implementation used slightly different tools each with its own advantages. When coding their model, Bourdais, Galinier, Saremi et al. [35], Le et al. [45], Hooshangi-Tabrizi et al. [51], Tohidi et al. [32], and Pesant [13] used C++. White et al. [18] and Saremi et al. [36] implemented theirs in C#. Rosenbloom and Goertzen [19] wrote their version in BASIC, with further work done in PASCAL. Santibáñez, Begen, and Atkins [34] also used VBA. White and White [3], and Diamant, Milner, and Quereshy [39] implemented theirs in Java with an AWT interface. Drysdale, Singh, and Goldenberg [23] built their Gaussian Process Regression using GPyTorch and the Adam optimizer. Camiat et al. [31] and Benzaid et al. [50] utilized Julia. Matlab was used by Wang et al. [37] and Roshanaei et al. [2]. When developing their machine learning model, Rozario and Rozario [25] and Naderi et al. [21] used Python. Legrain, Bourab, and Lahrichi [27] opted to implement their model in Excel to ease transition into using their software. There tended to be a trend for lower-level languages, with C++ being the most common. This was likely for two main reasons; the first being that most implementations were run on limited hardware that was not very powerful. To get the most out of it resources needed to be managed efficiently. Additionally, speed of completion is a major factor of how close to optimality one can get, so it is important to write the fastest code possible.

In addition to the languages used to code the model, a solver was needed to produce a solution. The most common solver by far was CPLEX used by Bourdais, Galinier, and Pesant [13], Legrain, Bourab, and Lahrichi [27], Benzaid et al. [50], Patrick et al. [15], Savage et al. [24], Hooshangi-Tabrizi et al. [51], Camiat et al. [31], Tohidi et al. [32], Diamant, Milner, and Quereshy [39], Gendreau, and Pesant [16], Chow et al. [33], Santibáñez, Begen, and Atkins [34], Godin and Wang [22], Saremi et al. [36], Saremi et al. [35], Oliveira et al. [41], and Naderi et al. [21]. CPLEX is a mathematical model solver written by IBM capable of tackling mixed-integer programming and linear programming. The other solver that was utilized was Gurobi. Gurobi was used by Wang et al. [37], Kandakoglu et al. [49], Zimmerman et al. [29], Roshanaei et al. [38], Roshanaei et al. [42], and Roshanaei et al. [2]. A competitor to CPLEX can approach the same kinds of relevant problems.

Aside from the main languages, many supplementary tools were used. The main tool used in these papers for database access was Microsoft Excel if it was mentioned. Santibáñez, Begen, and Atkins [34] used Microsoft Access. For simulations, Saremi et al. [36] and Saremi et al. [35] used a program called Rockwell Arena 12. Klassen and Yoogalingam [46] use OPTQUEST 2007 for their neural network.

As this is a focus on Canadian implementations (and from a Canadian perspective), all data comes from Canadian hospitals. Ontario was the most popular province with 18 papers working in collaboration with their hospitals. Quebec was the second most with 13. British Columbia hosted 3. The data comes from these sources. Bourdais, Galinier, and Pesant [13] acquired their data from the “Optimization of Health Care Management” research team in Montreal. Three hospitals from Montreal supplied data that was used to benchmark their program. White et al. [18] and White and White [3] built their programs for the Internal Medicine Clinical Teaching Unit at the Ottawa Hospital. Patrick et al. [15] also collaborated with the Ottawa Hospital, more specifically the Department of Pathology and Laboratory Medicine, to create their software. Hahn-Goldberg et al. [47] conducted a case study alongside the Odette Cancer Centre in Toronto. Tohidi et al. [32] gathered simulation data from a university health centre in Montreal. Jaumard et al. [20] worked with the Royal Victoria Hospital of Montreal, which not only supplied data but assisted in creating rules and constraints. Drysdale, Singh, and Goldenberg [23] got their data from The Hospital for Sick Children, Toronto, Ontario. Gendreau et al. [17] worked in collaboration with five hospitals: Jewish General Hospital (JGH), Charles-Lemoyne Hospital (CLH), Santa-Cabrini Hospital (SCH), Sacré-Cœur Hospital (SaCH), and Côte-des-Neiges Hospital (CNH). Beaulieu et al. [14], and Camiat et al. [31] both worked more in depth with Sacré-Cœur Hospital in Montreal. Hooshangi-Tabrizi et al. [51] aquired historical data from the Segal Cancer Centre. Carter et al. [1] interviewed six hospitals in the greater Montreal area, and then performed case studies on two hospitals: the Charles-Lemoyne Hospital and the Jewish General Hospital. Rousseau, Gendreau, and Pesant [16] also performed two case studies at the Santa Cabrini Hospital emergency room, Montreal and Côte-des-Neiges Geriatric Hospital. Savage et al. [24] worked alongside the Thunder Bay Regional Health Sciences Centre (TBRHSC) ED. Diamant, Milner, and Quereshy [39] had their work prompted by the Bariatric Surgery Program at Toronto Western Hospital. Rozario and Rozario [25] got their data from Oakville Trafalgar Memorial Hospital, Ontario. Wang et al. [37], Roshanaei et al. [38], Roshanaei et al. [42], and Roshanaei et al. [2] worked alongside the University Health Network (UHN), which consists of Toronto General Hospital (TGH), Toronto Western Hospital (TWH), and Princess Margaret Cancer Center (PMCC). Azari-Rad et al. [26] also worked with this cluster of hospitals but only used data from TGH. Chow et al. [33] got their data from the Royal Jubilee Hospital (RJH) in Victoria, BC. Santibáñez, Begen, and Atkins [34] worked with The Fraser Health Authority (FHA). Zimmerman et al. [29] worked with Vancouver Coastal Health. Saremi et al. [35] and Saremi et al. [36] do not name any specific hospitals but merely claim a major Canadian hospital. Legrain, Bouarab and Lahrichi [27] worked with Notre-Dame and Sainte-Justine to gather rulesets for their models. Kandakoglu et al. [49] worked alongside nephrologists at the Ottawa Hospital. Ma et al. [48] had a regional cancer centre in British Columbia collaborate to make a decision support system. Benzaid et al. collaborated with Centre Hospitalier Universitaire de Montreal. Finally, Le et al. [45] worked alongside the hematology-oncology clinic in the Regional Hospital at Trois-Rivières.

From this data, some trends can be noticed. There is a clear priority of cities such as Toronto, Montreal, and Ottawa. A very large majority of data comes from these three places. Additionally, there is a large bias towards heavily developed and urban areas, with few papers looking at smaller, more rural, hospitals. Papers working alongside Ontario Hospitals tended to prefer nurse scheduling and physician scheduling while operating rooms scheduling typically worked with Montreal and other Quebec based cities.

7. Commercial Software

With scheduling being such a universal problem, the door has been opened for commercial software to address this issue. There are dozens, if not hundreds of competing software on the market, and here are a few to be highlighted.

The first we will look at is Amion [53]. Amion is a physician scheduling program that boasts being used by over 250,000 providers. They offer the ability to schedule staff automatically, create staffing constraints and patterns, schedule both residents and attendings, and more. This offers the opportunity to standardize and sync schedules across an entire department. Over a hundred unique places have used Amion to improve their scheduling.

MeshAI [54] is another program in the field that serves thousands of healthcare workers. It can schedule all staff automatically and optimally. This promises the ability to make schedules seamlessly and painlessly. They claim to be able to reduce scheduling time by as much as 80%. MeshAI has worked with entities such as Kingston Community Health Centres, EPIC Primary Health, and Louisiana Women’s Healthcare.

A third contender is PetalMD [55]. This program is used by 37,000 physicians and automatically constructs fair and balanced schedules. As with the others, constraints are programmable into the app, allowing for flexibility and accessibility. Likewise to MeshAI, they can reduce scheduling time by 80%. Additionally, PetalMD has done several case studies on the benefits of optimized scheduling and has worked closely with various hospitals including Jewish General Hospital, Vancouver Coastal Health & Providence Health Care, and the Children’s Hospital of Eastern Ontario.

A final look will be given to Lightning Bolt [56]. Lightning Bolt uses AI to create optimized schedules, with specializations in several areas such as anesthesiology, cardiology, etc. This specialization allows more control over how the schedule is made and what rules can be put in place. Anesthesiology may care more about rotations, while cardiology may require a focus on specialty scheduling. Lightning Bolt has helped customers like John Hopkins and Providence.

This is just a sample of the options that are available to the healthcare workers for scheduling. All offer the ability to create optimized and automatic schedules for your department, freeing up time, money and labour.

8. Future Work

As one can see, there has been a very diverse set of solutions being used to tackle the problems above, most of which were able to improve upon current methods and more accurately allocate resources. Many different ideas have been explored on how to efficiently optimize the solutions generated by a programming model, most frequently neighbourhood searches and tabu search. Other metaheuristic algorithms such as particle swarm optimization, genetic algorithms, and more have only little to no representation here, while research has been done on these algorithms, none has been done in this domain. Future researchers could investigate more efficient ways to improve upon solutions. The creation of the actual mathematical model is a fairly fleshed-out process across these papers, so less effort would need to be directed towards that. Additional ways to reduce the problem, however, is another important area. Decomposition of problems into subproblems through processes such as Bender’s Decomposition or Column Generation allow more flexible, generic, and complex models by allowing easier computation. By exploring these topics more advanced models could be generated and their effects explored.

Another area of interest that is more specific to this domain surrounds the research that focuses on making predictions of stochastic elements. Being able to know the approximate number of patients, when they will arrive, how long their duration will be, etc. can improve models beyond simply improving a solution. This helps define the boundary of where the solution should be improved in the first place. There were a few papers that looked into these problems, but there are still many more ideas that have yet to be explored. One area of further research could be to use machine learning to attempt to model these elements. Another would be to compare different simulation techniques to identify which performs the best in Canadian healthcare environments. The more accurately the models can gauge these variables, the more accurate the final solutions will be.

Exploring how to encode data is an area that most papers have mostly neglected. A large majority of papers encode their schedules by creating a sequential list of timeslots. As Naderi et al. [21] has demonstrated, there are other paradigms to consider that can lead to faster and more effective models. Le et al. [45] and Bourdais, Galinier, and Pesant [13] also touch on this idea by suggesting a horizontal scheduling method (per week or schedule) and comparing it to a vertical (per day) method. Each version of the data has different benefits. Computation time could be improved by changing the method of encoding the data.

Collaborative work also looked very promising as an area that warrants more explanation. When treating hospitals as a network more resources are available for allocation. Scheduling becomes a collaborative process, and so lesser utilized areas can redirect resources to the location that needs them most. Roshanaei et al. [2] are the only people who explore this area, and they have positive results to back it up. Canadian hospitals that work together should be able to lessen the burden each one experiences individually.

Additionally, there is very little representation of hospitals that do not originate from Montreal, Toronto, and Ottawa. Smaller hospitals tend to have different problems compared to larger, more urban ones. Branching out and exploring hospitals that represent different demographics could offer valuable insights that are not available in large cities.

Many papers also fail to follow up with how their scheduler impacts the hospital. There is no data to validate how these schedulers affect metrics such as well being or patient outcome over longer periods of time. This data would be beneficial in order to explore which constraints are valued by staff and quantify the impacts each choice has. Adoption is limited once the research period has ended, work could be done on how to encourage use beyond the trial period. Generic solvers may be a step in that direction.

Finally, one can take the information these papers (and many others) and contain and use it to produce further medical guidelines. Distilling information down into guides allows medical professionals to reference and utilize it far better than doing the research themselves. Klassen and Yoogalingam [46] explored this idea of trying to create rules by creating the schedules and analyzing the patterns that they created. Future work would be built on top of the information created before. This also allows it to be utilized in other software such as clinical decision support systems and informatics software, which can allow this research to branch out beyond just scheduling.

9. Conclusions

Scheduling is one of the most important problems that hospitals experience, and one that offers the most benefits when improved. Throughout these papers, many solutions have been offered, with many different approaches and many different tools. Some of them are based on case studies of nearby hospitals, while others used historical data. This is all in the pursuit of more efficiently allocating resources and creating schedules that can help the most people.

Nearly all had positive results and were able to improve on current methods of rostering. The benefits to pursuing this include (but are not limited to): improving staff morale and productivity, allowing more patients to receive the help they require, more effective use of resources, and ultimately more lives saved. The costs of doing so are often minimal with minor upfront development. Tools such as CPLEX, Gurobi, and more, exist to help solve these problems, and other software such as Hibiscus have been purpose-made for this problem.

Despite the benefits listed above, in almost all cases the methodologies were not adopted, or not stated to be adopted, in the healthcare centres that were worked with.

Overall, the field is very active in tackling scheduling issues and every improvement made has a tangible net benefit.