# How to tackle large nurse scheduling problem?

I have a nurse-scheduling type of problem with a time span of a year and many employees.

## Formulation

My main variables are: \begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to task } t \\ 0 \text{ otherwise} \end{cases}\\w_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to any task in day } d \\ 0 \text{ otherwise} \end{cases}\\v_{e,d} &= \begin{cases}1 \text{ if employee } e \text{ is on vacation on day } d \\ 0 \text{ otherwise} \end{cases}\end{align} Hired days: $$H_{e} = \text{last work day}-\text{first work day}$$ Employee vacations: $$V_{e} = \left\lceil\frac{H_{e}\cdot31}{366}\right\rceil$$

## Details

• I cannot divide the problem more in terms of time as there are some constraints and variables that need to be calculated yearly.
• I have the following symmetry breaking constraint: $$\sum_{t\in T}{x_{e,t}} \le \sum_{t\in T}{x_{e-1,t}}$$
• I have divided the problem into cliques of related tasks and employees.
• I can provide more details about my variables and constraints if needed.

## Question

Is there a better way to formulate this problem?

Maybe I could add more symmetry breaking or redundant constraints that could speed up the solving (I'm using OR-Tools).

I also feel like I should assign group of tasks instead of individual tasks, is that a good idea?

Edit:

With this formulation I have around 159245 variables and 478303 constraints with 80 employees.

• can you give us some insights how many variables and constraints you have? – JakobS Oct 18 '19 at 15:19
• Info added, but I think that I will remove this question in favor of specific questions about how I implement some of the constraints. – Stradivari Oct 18 '19 at 15:25
• Can you add a minimal working example for the code you have using or-tools? This would make it easier to give you hints what to improve. – JakobS Oct 18 '19 at 19:03