On-Call Weekends? (Linear Programming)

Question

There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that

• every person will have at least two free weekends after an on-call weekend
• on-call pairs will always change

Possible pairs are (persons are 1...9), total 36 different pairs: 12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89

How can i solve this with Excel solver, or GLPK?

> lp beginner, Finland

Answer 1

Again, it is in my opinion impossible to do this as an LP. However we can try a MIP formulation.

Let's use the following notation:

• $x_{i,t} \in \{0,1\}$ is assigning person $i$ to weekend $t$
• $y_{i,j,t} \in \{0,1\}$ is assigning pair $(i,j)$ to weekend $t$. There are 36 pairs possible and that also dictates our planning window $t$.

The obvious constraints on $y$ are:

$$\begin{align} &\sum_{(i,j) \in P} y_{i,j,t} = 1 & \forall t \>\>& \text{(one pair per weekend)} \\ &\sum_t y_{i,j,t} \le 1 & \forall (i,j) \in P \>\> & \text{(no repeats of pairs)}\end{align}$$

The constraint on $x$ is that we need $x_{i,t}=1 \implies x_{i,t+1}=x_{i,t+2}=0 $ . This we can formulate surprisingly simple as: $$ x_{i,t}+x_{i,t+1}+x_{i,t+2} \le 1 \>\> \forall i,t $$ (The equivalence of these two requires a bit of thought).

Finally we need to connect $x$ and $y$. This is done by $y_{i,j,t}=x_{i,t} \cdot x_{j,t}$. This binary multiplication can be linearized as:

$$\begin{align} & y_{i,j,t} \le x_{i,t} & \forall (i,j) \in P, \forall t\\ & y_{i,j,t} \le x_{j,t} & \forall (i,j) \in P, \forall t\\ & y_{i,j,t} \ge x_{i,t}+x_{j,t}-1 & \forall (i,j) \in P, \forall t \end{align}$$

There is no objective. This MIP model can be solved with any MIP solver (although Excel solver has size limits that are probably too small for this problem). As there is no objective the solver will stop at the first integer feasible point. A constraint programming (CP) solver would make the model simpler to express.

Answer 2

Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:

(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).