How to tackle large nurse scheduling problem?

Question

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.

Answer 1

There are many approaches to formulate nurse scheduling model. In practice, MIPs and some heuristics have frequently been used. AFAIK, for large scale MIPs, column generation technique can be applied.

Some useful references are:

• A workforce scheduling problem (column generation)
• A Flexible Mixed Integer Programming framework for Nurse Scheduling
• Employee Scheduling using OR-Tools
• Planning and Scheduling in Manufacturing and Services. Workforce Scheduling. chapter 13 by Michael L. Pinedo

I hope, they would be useful.