# A Review of the Scheduling Problem within Canadian Healthcare Centres
## 3 Schedule Overview
### 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 [PERSON], [PERSON], and [PERSON] [13], [PERSON] et al. [14], [PERSON] et al. [15], [PERSON], [PERSON], and [PERSON] [16], [PERSON] et al. [17], etc. are the categories below:  
* Rules pertaining to demand of shifts and availability of staff. * Rules pertaining to how much each staff work. * Rules regarding the distribution of shifts. * Rules regarding the pattern that shifts take.