# Limit number of switches in employee scheduling problem

Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational constraints. Note that each employee can work at any position but only one shift per day totally.The main objective here is to minimize the total shift switches within week. First I shall introduce my variables and the constarints and then how I formulated it mathematically.

Binary variables:

1. Employee: $$x_{i}$$, i=1:N
2. Working day per employee: $$y_{i,j}$$, i=1:N | j=1:7
3. Wroking day/shift/position per employee: $$z_{i,j,k,l}$$, i=1:N | j=1:7 | k = 1:3 | l = 1:2
4. Shift switch per employee per day: $$s_{i,j,k}$$, i=1:N | j=1:7 | k = 1:3

Constraints:

1. One shift per day per employee: $$\sum_{k,l} z_{i,j,k,l} \leqslant y_{i,j} \ \ \forall i,j$$
2. One position per day per employee: $$z_{i,j,k,1}+ z_{i,j,k,2} \leqslant1 \ \ \forall i,j,k$$
3. Maximum working days per employee (6 days): $$\sum_{j} y_{i,j} \leq x_{i}\cdot D_{max} \ \ \forall i=1:N$$
4. Minimum working days per employee (5 days): $$\sum_{j} y_{i,j} \geq x_{i}\cdot D_{min} \ \ \forall i=1:N$$
5. Comply with weekly demand (D): $$\sum_{i} z_{i,j,k} = D_{j,k,l} \ \ \forall j,k,l$$
6. Detect any shift switch day over day: $$\sum_{l}z_{i,j,k,l}- \sum_{l}z_{i,j-1,k,l} \leqslant s_{i,j,k} \ \ \forall i,j=2:7,k$$

I followed this method to introduce continuity in shift assignment and reduce switches

Objective:

Minimize shift switches day over day across all employees:$$min \sum_{i,j,k}s_{i,j,k} \ \ \forall i,j=2:7,k$$

Running this in R with ompr package I get this results: Employees are placed to rows and columns depict the day of the week. Values denote the shift an employee is assigned to. Missing values (NA) correspond to employee's day off according to the constraints.

This is not the best solution, at first glance, this can be solved with very few employees having shift change within week and the rest to be assigned to a single shift throughout the week. I guess this is due to the fact that any day off followed by a shift assignment is considered as change. Any thoughts?

• typo in constraint 6. (updated) Jun 23 '20 at 13:19
• Even with your change from plus to minus in constraint 6, it is not correct when you can have days off. What you have would force $s_{i,j,k}=1$ when the employee works on day $j$ but is off on day $j-1$. Jun 23 '20 at 13:29

You can omit constraint 2 because it is dominated by constraint 1.

Constraint 6 is not correct. For consecutive days, you want $$\sum_l z_{i,j,k,l}+\sum_l z_{i,j-1,k_2,l}-1\le s_{i,j,k},$$ where $$k\not= k_2$$.

For a day off in between, you want $$\sum_l z_{i,j,k,l}+(1-y_{i,j-1})+\sum_l z_{i,j-2,k_2,l}-2\le s_{i,j,k},$$ where $$k\not= k_2$$.

For two days off in between, you want $$\sum_l z_{i,j,k,l}+(1-y_{i,j-1})+(1-y_{i,j-2})+\sum_l z_{i,j-3,k_2,l}-3\le s_{i,j,k},$$ where $$k\not= k_2$$.

• First of alI I have to admit your loyalty :) to all of my questions. I really appreciate this! I guess I can follow your thought but what I miss here is the concept. I do not know apriori where I expect to spot the day off(s), start/end/mid week. I can not implement all suggested constraints simultaneously, right? Jun 23 '20 at 13:53
• Yes, you should implement all three suggested constraints simultaneously. The idea is to avoid a pattern like $(w_j,w_{j+1},w_{j+2})=(1,0,1)$ where $w$ is binary, you equivalently want to avoid $(w_j,1-w_{j+1},w_{j+2})=(1,1,1)$, which you can prohibit via a linear "no-good" constraint $w_j+(1-w_{j+1})+w_{j+2} \le 3 - 1$. By the way, you can replace $s_{i,j,k}$ with just $s_{i,j}$. Jun 23 '20 at 15:13

@RobPratt, thank for the clarification. I tried to incorporate the above into my MILP model but I do not get a feasible solution even after half an hour of searching which is strange. Following your explanation, I ended up with something different that returns a feasible solution quickly. Here it is: Introduce decision variable: $$s_{i,k}$$.

and this is the constraint I propose: $$\sum_{j,l} z_{i,j,k,l} \le 7\cdot s_{i,k}$$

If the shift is assigned at least one day then the corresponding decision variable is enabled. Since I want the minimum number of switches I need an objective that is responsible to assign a single shift per employee as much as possible.

Objective function can be altered to: $$\sum_{\min} s_{i,k}$$ This way I can minimize switches in terms of shift regardless of what happens within the week. What is your opinion?

• This looks reasonable, although you might also consider the stronger "disaggregated" formulation $z_{i,j,k,l} \le s_{i,k}$. Jun 30 '20 at 11:13
• Note that your reformulation relies on the fact that every employee works at least one shift, as enforced by constraint 4. Jun 30 '20 at 12:56
• If I use the disaggregated formulation, then this is just simply imposing same shift across days per driver, right? I do not want this because in some cases this is not feasible. Jul 1 '20 at 12:54
• Both your proposed constraint and the disaggregated one enforce the logical implication $z_{i,j,k,l}=1 \implies s_{i,k} = 1$. In words, if employee $i$ on day $j$ works shift $k$ in position $l$, then employee $i$ works shift $k$ at least once. I had mistakenly interpreted the $7$ as the number of $j,l$ combinations, which is instead $7\cdot 2=14$, so the disaggregated form is not stronger. Adding up the disaggregated constraints yields your proposed constraint, except with $14$ instead of $7$. Neither form imposes the same shift across days per driver. Jul 1 '20 at 13:57