# A Review of the Scheduling Problem within Canadian Healthcare Centres
## 4 Hospital Scheduling in Depth
### General Staffing/Nurse Staffing
#### 4.1.2 Papers
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 [PERSON], [PERSON] and [PERSON] [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. [PERSON] 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. [PERSON], [PERSON], and [PERSON] [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. [PERSON] 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.