Custom Nurse Rostering Problem

Question

_{I've asked this question also on Operations Research 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}^n x_{i0k} = n{\rm Morning}&\quad\forall k\\&\quad\sum_{i=0}^n x_{i1k} = n{\rm Afternoon}&\quad\forall k\\&\quad\sum_{i=0}^n x_{i2k} = n{\rm Night}&\quad\forall k\end{alignat}

---

UPDATE (17/01/2020) thanks to @lonza leggiera

Let $\ W\ $ a set of weekend days and $\ H\ $ a set of holidays. Actual model: $$ \text{mimimize } \sum_{j=0}^1\sum_{i=0}^n \sum_{k=1}^{30} x_{ijk}\left(1-x_{i(j+1)(k+1)}\right)\ $$

$$ \sum_{i=0}^{n} x_{i0k}=nMorning \forall k $$

$$ \sum_{i=0}^{n} x_{i1k}=nAfternoon \forall k $$

$$ \sum_{i=0}^{n} x_{i2k}=nNight \forall k $$

$$ \sum_{j=0}^{2} x_{ijk}<=1 \forall i,k $$

$$ x_{i2k} + \sum_{j=0}^{2} x_{ij(k+1)}<=1 \forall i,k $$

$$ \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)\ \ \text{ for all }\ i_1,i_2\\ \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)\ \ \text{ for all }\ i_1,i_2\ . $$

Answer 1

You've correctly formulated the constraints corresponding to dot points $3$ to $5$ in your description of the problem. However:

• Your objective function has the fixed value $$ 31\left(n_\text{morning}+ n_\text{afternoon}+ n_\text{night}\right)\ ,$$ independent of any values chosen for your decision variables, so nothing you do can make its value any smaller.
• You have nothing in your formulation corresponding to your dot points $7$ to $10$. Dot points $7$ and $8$ are clearly constraints, which you can formulate as $$ \sum_{j=0}^2x_{ijk} \le 1\ \ \text{ for all }\ i,k $$ and $$ x_{i2k}+ \sum_{j=0}^2x_{ij(k+1)}\le1 \ \ \text{ for all }\ i,k\ . $$
• Dot point $9$, as stated in the problem description, appears to require a pair of hard constraints. To formulate them mathematically, you need to introduce a set $\ W\ $ of weekend days and $\ H\ $ of holidays. The constraints could then be written as$$ \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)\ \ \text{ for all }\ i_1,i_2\\ \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)\ \ \text{ for all }\ i_1,i_2\ . $$ However, I believe that these constraints would be quite likely to make the problem infeasible, so it might be advisable to replace them with an objective of minimising the maximum difference between their two sides.
• Dot point $10$ is currently stated as an aspiration, rather than a hard constraint, although the condition that every night shift be followed by a rest day has already been stated as a hard constraint in dot point $8$. Minimising the total number of times the other two conditions are violated would nevertheless appear to be a suitable objective. The quantity $\ x_{i0k}\left(1-x_{i1(k+1)}\right)\ $ is $1$ if nurse $i$ has a morning shift on day $k$ but doesn't have an afternoon shift on the next day, or zero otherwise. Thus $$ \sum_{i=0}^n \sum_{k=1}^{30} x_{i0k}\left(1-x_{i1(k+1)}\right) $$ is the number of times (in January) that a morning shift is not followed by an afternoon shift. Likewise $$ \sum_{i=0}^n \sum_{k=1}^{30} x_{i1k}\left(1-x_{i2(k+1)}\right)\ . $$ is the number of times an afternoon shift is not followed by a night shift. Thus your objective could be formulated as: $$ \text{mimimize } \sum_{j=0}^1\sum_{i=0}^n \sum_{k=1}^{30} x_{ijk}\left(1-x_{i(j+1)(k+1)}\right)\ . $$