# A Review of the Scheduling Problem within Canadian Healthcare Centres
## 3 Schedule Overview  
### 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(a)) \tag{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(a)) \tag{2}\]  
\[s.t.\ h(a,t)\ \forall a\in A,t\in T,h\in H \tag{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.