# Rostering problem - variation of the post office problem

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