Suppose I have $N$ staff members. I employ each of them for 5 days during the week. Each day, $i$, from Saturday to Friday requires $s_i$ staff members. I wish to maximize the number of staff who have two days in a row off each week. Each staff member is rostered to work the same days each week. I don't employ anymore staff than necessary on a given day. How do I turn this problem into an integer-linear program?

This is definitely a type of variation of the post office problem, but with a fixed number of employees.

So far, I have the following:

Let $x_i$ be the number of employees with the first day off on day $i$. The total number of employees with consecutive days of are then given by: $$ \frac{1}{2}[(x_1 + x_2) + (x_2 + x_3) + (x_3 + x_4) + (x_4 + x_5) + (x_5 + x_6) + (x_6 + x_7) + (x_7 + x_1)] $$ which means I am trying to maximize: $$ \sum_{i=1}^7 x_i $$

I am now not sure how to form the constraints.


I would do it as follows.

First, define the set $I$ of possible shifts with two days off in a row :

  • shift $1$ : mondays and tuesdays off
  • shift $2$ : tuesdays and wednesdays off
  • shift $3$ : wednesdays and thursdays off
  • etc

Complete with other types of shifts $J$ such as

  • shift $i$ : mondays and wednesays off

Second, define binary variables $y_i \in \{0,1\}$ that take value $1$ if and only if shift $i$ is selected, $i \in I\cup J$.

Now, you have everything you need. You want to maximize the number of shifts selected from $I$: $$ \sum_{i \in I} y_i $$ subject to

  • You need $s_t$ shifts on day $t$ (among the shifts that have a working day on $t$) : $$ \sum_{i \in I\cup J | t \in i} y_i = s_t \quad \forall t=1,...,5 $$
  • You need a total of $N$ shifts (one for each staff member): $$ \sum_{i \in I\cup J } y_i = N $$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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