Custom Nurse Rostering Problem

Question

_{I've asked this question also on Math Stack Exchange.}

It's a custom nurse rostering problem:

• $N$ is a set of nurses;
• $S$ is the set of shift-type (morning, afternoon, night, rest)
• $n_\mathrm{Morning}$ is the number of nurses required every day to cover a morning;
• $n_\mathrm{Afternoon}$ is the number of nurses required every day to cover an afternoon;
• $n_\mathrm{Night}$ is the number of nurses required every day to cover a night;
• Every shift lasts $8$ hours;
• Every nurse can work only for one shift in a day;
• After every night a nurse must have a rest day;
• Rest at the weekend and on holiday have to be balanced between all nurses;
• I would like that after every morning there will be an afternoon, after an afternoon a night and after a night a rest day.
• I would like to plan shifts with a month frequency.

What are the decision variables and the objective function that I have to use? Can anyone help me to write it?

I can define the quantity $x_{ijk}=1$, if nurse $i$ works on shift $j$ on day $k$, and $0$ elsewhere. But how can I balance holiday and rest days between other nurses?

---

UPDATE (16/01/2020)

This is the actual model that I have formulated, is this right for covering constraints $3$ to $5$?

• $j$ is an element of $S$, coded as: $0=\rm Morning$, $1=\rm Afternoon$ and $2=\rm Night$;
• $k$ is an element of the set of days of January.

\begin{alignat}2\min&\quad\sum_{i=0}^n\sum_{j=0}^2\sum_{k=1}^{31}x_{ijk}\\\text{s.t.}&\quad\sum_{i=0}^nx_{i0k}=n_{\rm Morning}&\quad\forall k\\&\quad\sum_{i=0}^nx_{i1k}=n_{\rm Afternoon}&\quad\forall k\\&\quad\sum_{i=0}^nx_{i2k}=n_{\rm Night}&\quad\forall k\end{alignat}

---

UPDATE (17/01/2020) - Thanks to @lonzaleggiera on Math Stack Exchange.

Let $W$ be a set of weekend days and $H$ be a set of holidays. The actual model is given by \begin{alignat}2\min&\quad\sum_{j=0}^1\sum_{i=0}^n\sum_{k=1}^{30}x_{ijk}\left(1-x_{i(j+1)(k+1)}\right)\\\text{s.t.}&\quad\sum_{i=0}^nx_{i0k}=n_\text{Morning}&\forall k\\&\quad\sum_{i=0}^nx_{i1k}=n_\text{Afternoon}&\forall k\\&\quad\sum_{i=0}^nx_{i2k}=n_\text{Night}&\forall k\\&\quad\sum_{j=0}^2x_{ijk}\leq1&\forall i,k\\&\quad x_{i2k}+\sum_{j=0}^2x_{ij(k+1)}\leq1&\forall i,k\\&\quad\sum_{k\in W}\left(1-\sum_{j=0}^2x_{i_1jk}\right)=\sum_{k\in W}\left(1-\sum_{j=0}^2x_{i_2jk}\right)&\forall i_1,i_2\\&\quad\sum_{k\in H}\left(1-\sum_{j=0}^2x_{i_1jk}\right)=\sum_{k\in H}\left(1-\sum_{j=0}^2x_{i_2jk}\right)&\forall i_1,i_2.\end{alignat}

These are my current doubts:

1. For the last two hard constraints to balance weekend and holidays, the problem will probably become infeasible. To integrate them in the current objective function, do I have to multiply the current objective function with the maximum difference between the two sides?
2. If I find an empty polyhedron replacing the two hard constraints can I replace $=$ (points $3$, $4$ and $5$) with $>$?
3. If I solve this model every month, how can I remember the past decisions to have continuous balancing?

Answer 1

1. You could rewrite the two last constraints as $$ f(i_1,i_2)-g(i_1,i_2) = e_{i_1i_2} $$ where $e_{i_1i_2}\in \mathbb{R}^+$ is a continuous variable that equals the difference between the left hand term and right hand term (and so $f(i_1,i_2)$ is your left hand term, and $g(i_1,i_2)$ your right hand term), and then minimize this variable in the objective function (eventually multiplied by a coefficient).

2. No, if you are working with linear programming, you cannot use the $\{<,>\}$ signs.

3. I think you need to work on a rolling horizon, that is, write your model for the the first month, and after week $1$, re-solve it. After week $2$, solve it again, and so forth. This of course implies that when you solve your problem, only the first week is definitely set. The other weeks are temporary and may change if balancing is required.

---

Although your model looks correct, have you considered other formulations such as a Dantzig-Wolfe decomposition? They fit your problem quite well :

Let $\mathcal{S}$ be the set of feasible shifts (e.g., over a week, or why not a month if it is relevant), and let $y_s$ be a binary variable that takes value $1$ if and only if shift $s\in \mathcal{S}$ is selected. Your problem then requires that :

• shifts are satisfied each day :

$$ \sum_{s \in \mathcal{S} \mid j \in s, t\in s} y_s = n_{j} \quad \forall j \in \{\mbox{morning},\mbox{afternoon},\mbox{night}\}, \quad \forall t=1,\dots,7 $$ (this means that for each day, and each shift type, you only sum on the shifts that have a working period on that day, for that shift type)

• you cannot have more than $\mid N \mid$ shifts ($1$ shift per nurse per week) : $$ \sum_{s \in \mathcal{S} } y_s \le|N| $$

To balance the shifts, you could define a coefficient $c_{s_is_j}$ for each pair of shifts that is more or less important if the shifts are pairwise balanced (e.g., $c_{s_is_j}=0$ if the shifts are balanced, $1$ if they are moderately unbalanced and $2$ if they are unbalanced). And so you could minimize $$ \sum_{s_i \in \mathcal{S}}\sum_{s_j \in \mathcal{S}} c_{s_is_j} \delta_{s_is_j} $$ where $\delta_{s_is_j}$ is another binary variable that takes value $1$ if and only if shifts $s_i, s_j$ are both selected (so you would have to add $y_{s_i}+y_{s_j} \le \delta_{s_is_j} +1$ to the model).

Of course this implies that you have generated your feasible shifts before hand (this is not too difficult). Alternatively, you could generate them dynamically if you are familiar with column generation.