Suppose I have a model for creating a nurse's duty roster. The model has the indices $i$ for the person, $t$ for the day and $s$ for the shift. I have the binary variable $x_{its}$ which indicates whether a person is working or not. Now I want to "capture" the monotony of working hours in a new variable. For example, if a nurse works the same shift for 14 days, with or without break days, then this should be stored in a new binary variable. How could I do this?

  • $\begingroup$ Is a shift a sequence of hours, or days? $\endgroup$
    – Kuifje
    May 11 at 11:21
  • $\begingroup$ A sequence of hours, a day has three shifts $\endgroup$ May 11 at 11:24
  • $\begingroup$ Do you mean exactly 14 days or at least 14 days? $\endgroup$
    – RobPratt
    May 11 at 13:39
  • $\begingroup$ @RobPratt for exactly 14 days, but I want to define this monotony variable $y_{id}$ for every $i$ and day $t$, so f.e on day 15, the shifts were the same for person $i$, which yield $y_{i15}=1$, but now on day 15 the shift changes, which means $y_{i16}=0$, as the 14 days prior to day 16 were not always the same. So I want to show each day for each person whether the last 14 days have been monotonous. $\endgroup$ May 12 at 7:23

1 Answer 1


Define a new binary variable $y_{its}$ that takes value $1$ if nurse $i$ works the same shift $s$ for $n$ consecutive days (exactly), starting on day $t$.

You want to enforce: $$ \neg x_{i,t-1,s} \wedge \left(\bigwedge_{j=t}^{t+n-1} x_{ijs}\right) \wedge \neg x_{i,t+n,s} \implies y_{its}\quad \forall i,s,t $$ Or equivalently via CNF: \begin{align} &\neg \left(\neg x_{i,t-1,s} \wedge \left(\bigwedge_{j=t}^{t+n-1} x_{ijs}\right) \wedge \neg x_{i,t+n,s}\right) \vee y_{its}\quad &\forall i,s,t \\ & x_{i,t-1,s} \vee \left(\bigvee_{j=t}^{t+n-1} \neg x_{ijs}\right) \vee x_{i,t+n,s} \vee y_{its}\quad &\forall i,s,t \\ &x_{i,t-1,s} + \sum_{j=t}^{t+n-1} (1- x_{ijs}) + x_{i,t+n,s} + y_{its} \ge 1\quad &\forall i,s,t \\ & \sum_{j=t}^{t+n-1} x_{ijs} \le x_{i,t-1,s} + x_{i,t+n,s} + y_{its} + (n-1) \quad &\forall i,s,t \end{align}

If you need to enforce the converse: $$ y_{its} \implies \neg x_{i,t-1,s} \wedge \left(\bigwedge_{j=t}^{t+n-1} x_{ijs}\right) \wedge \neg x_{i,t+n,s} \quad \forall i,s,t $$ The same method yields: \begin{align} y_{its} + x_{i,t-1,s} &\le 1 &\forall i,s,t\\ y_{its} + x_{i,t+n,s} &\le 1 &\forall i,s,t\\ y_{its} &\le x_{ijs} &\forall i,s,t, j\in\{t,\cdots,t+n-1\}\\ \end{align}

  • $\begingroup$ Thank you very much. Can I also definie $y_{is}$ as $y_{it}$, indicating that the monotony occurs in day $t$? And for which indices is the upper constraint defined? I guess it is not $\forall t\in T$? $\endgroup$ May 11 at 11:41
  • $\begingroup$ you could use $y_{is}^t$ to indicate that the monotony occurs for nurse $i$ with shift $s$ on days $t,...,t+n-1$. $\endgroup$
    – Kuifje
    May 11 at 11:44
  • $\begingroup$ Indeed, the upper constraint is defined for $t=1,\cdots,|T|-n+1$. You need to be careful at the borders. For example, for $t=1$, replace $x_{i,0,s}$ by $0$. And same for $t=|T|-n+1$: replace $x_{i,|T|+1,s}$ by $0$. $\endgroup$
    – Kuifje
    May 11 at 12:23
  • $\begingroup$ Thanks. Can I also definie $z_{it}=\sum_{s\in S} y_{is}^t$, would this not add up? And can I also define the constraints for the last $n$ days and not to following one? $\endgroup$ May 11 at 13:10
  • $\begingroup$ In the first of the three inequality constraints, should $t$ be $t-1$? Also, since the inequalities test a streak of exactly $n$ days with the same shift starting on day $t$, shouldn't $y$ have a subscript $t$? $\endgroup$
    – prubin
    May 11 at 15:09

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.