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?
  • $\begingroup$ Original: math.stackexchange.com/questions/3505141/… $\endgroup$
    – Stradivari
    Commented Jan 16, 2020 at 14:41
  • $\begingroup$ Hi, welcome to OR.SE. Yes, with those variables you'll be able to model the constraints mentioned at your post. But depending on how you want to model the one about balanced rest on weekends and holidays between all nurses, it could be helpful to create some auxiliary variables and/or slack variables. As you want to plan for a whole month I guess the problem instance could become large, in that case you should consider using standard approaches like column generation. You could also experiment replacing the equality constraint (on the 3 equalities you wrote) by greather-than-equal constraints. $\endgroup$
    – dhasson
    Commented Jan 16, 2020 at 15:07
  • $\begingroup$ Mmm but how can I assure, for example, that if nurse $ x $ work on 31 December of year $ x $ then in the year $ x + 1 $ she doesn't work? I woulda perfect balancing $\endgroup$ Commented Jan 16, 2020 at 15:31
  • $\begingroup$ So you'd like the "Rest at the weekend and on holiday have to be balanced between all nurses" constraint to comprise long term, further than a month (the model's planning horizon)? To consider the situation you write, you could create an additional parameter, which indicates if the nurse worked the last day of the previous month (like a border condition). This parameter must comply with all the model's constraints such that each month's schedule gets consistently coupled with the next month's solution. You'll also need new constraints to link the variables with this border condition. $\endgroup$
    – dhasson
    Commented Jan 16, 2020 at 19:47
  • 1
    $\begingroup$ OK, you would prefer a perfect balance between the nurses' shifts. But how would you like to model the fulfilment of that condition? For example, some alternatives could be 1) penalizing the deviation from an average of nurse workload or 2 ) penalizing the difference between the maximum workload and the minimum one? $\endgroup$
    – dhasson
    Commented Jan 16, 2020 at 19:49

1 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.

  • 1
    $\begingroup$ Thank you for your detailed and formal answer. So, if I would rewrite the last two constraints my objective function will become: $$\min\sum_{i=0}^n\sum_{j=0}^2\sum_{k=1}^{31}x_{ijk} * e_{i_1i_2} * h_{i_1i_2}$$ where $ e_{i_1i_2} $ is the difference (left hand and right hand) of the weekend constraint and $ h_{i_1i_2} $ is the difference (left hand and right hand) of the holiday constraint? I don't have understood your third answer: If I solve the model on week1, then when I re-solve the model on week 2, how can I remember the decisions made on week1? $\endgroup$ Commented Jan 20, 2020 at 9:11
  • 1
    $\begingroup$ No, you need to keep your objective function linear. Separate the sum (one term for the holiday, one term for the weekend). $\endgroup$
    – Kuifje
    Commented Jan 20, 2020 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.