2
$\begingroup$

I have the following problem. I have a Nurse rostering problem and want to model the following. I have the indices $D$ (days), $I$ (nurse), $S$ (shift). My planning period $D$ is 28 days. Now I want to include weekend work without having to introduce new indices.

I would need the following constraints. In a period of 14 days, 1) one weekend must remain completely free and 2) once it must be completely occupied. So for the period from $d=1-14$ either a) work must be done on days 6-7 and not on 13-14 or b) the other way round. And the whole thing should be repeated every 14 days. Twice for 28 days. 3) In addition, after a weekend of work, Monday should be free. How do I get this modeled? I really have no idea how to start. The constraints should be compliant for an LP.

I have the variable $y_{id}$ which tells me whether nurse $i$ is working on day $d$ and $x_{ids}$ whether a nurse is working shift $s$ on day $d$.

This would be my idea for question 3: \begin{align}y_{i(t-1)}+y_{it}\le 1 \forall i \in I, t \in T \{8,\ldots,\mid T \mid - 6\}\end{align}

$\endgroup$

2 Answers 2

4
$\begingroup$

You want to enforce $$(y_{i,6} \land y_{i,7} \land \lnot y_{i,13} \land \lnot y_{i,14}) \lor (\lnot y_{i,6} \land \lnot y_{i,7} \land y_{i,13} \land y_{i,14}).$$ Rewriting in conjunctive normal form yields $$ (y_{i,6} \lor \lnot y_{i,7}) \land (y_{i,7} \lor y_{i,13}) \land (\lnot y_{i,13} \lor y_{i,14}) \land (\lnot y_{i,6} \lor \lnot y_{i,14}) ,$$ from which we immediately obtain linear constraints \begin{align} y_{i,6} + (1 - y_{i,7}) &\ge 1 \\ y_{i,7} + y_{i,13} &\ge 1 \\ (1 - y_{i,13}) + y_{i,14} &\ge 1 \\ (1 - y_{i,6}) + (1 - y_{i,14}) &\ge 1 \end{align}

This system simplifies to $$y_{i,6} = y_{i,7} = 1 - y_{i,13} = 1 - y_{i,14}.$$

$\endgroup$
2
  • $\begingroup$ Thank you @RobPratt. Is there any way i can formulate this in a more general manner? Assuming I have a planning horizon of 98 days or more, how can the whole thing be formulated in a more general way so that it is also valid for the longer period? $\endgroup$
    – Uni ewr
    Jan 9 at 7:45
  • $\begingroup$ Just add $14k$ to the second index of $y$: $$y_{i,6+14k}=y_{i,7+14k}=1-y_{i,13+14k}=1-y_{i,14+14k}$$ $\endgroup$
    – RobPratt
    Jan 9 at 13:53
0
$\begingroup$

In general for rotating periods a standard way to model (attributing to model by @Kuifje link)

$y_{i,k}+y_{i,k+7} = 1 \quad \forall u=0,1,2 \ \ \forall d=6,7 \ \ \forall k =7u+d$

$y_{i,k} = y_{i,k+1} \ \ \forall u=0,1,2 \ \ \forall k =7u+6$

$\endgroup$
1
  • 2
    $\begingroup$ Let's assume that day 1 is a Monday. For $u=0$ and $d=6$, your first constraint becomes $y_{i,6} + y_{i, 12} \le 1,$ meaning if you work on the first Saturday then you cannot work on the second Friday? $\endgroup$
    – prubin
    Jan 8 at 16:20

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.