Rostering problem - variation of the post office problem

Question

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.

Answer 1

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