2

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}

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Uni ewr
  • 21
  • 2

2 Answers2

4

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}.$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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? – Uni ewr Jan 09 '24 at 07:45
  • 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}$$ – RobPratt Jan 09 '24 at 13:53
0

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$

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • 2
    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? – prubin Jan 08 '24 at 16:20