3
$\begingroup$

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:

enter image description here

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ typo in constraint 6. (updated) $\endgroup$
    – Psyndrom Ventura
    Jun 23, 2020 at 13:19
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jun 23, 2020 at 13:29

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Psyndrom Ventura
    Jun 23, 2020 at 13:53
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – RobPratt
    Jun 23, 2020 at 15:13
1
$\begingroup$

@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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ This looks reasonable, although you might also consider the stronger "disaggregated" formulation $z_{i,j,k,l} \le s_{i,k}$. $\endgroup$
    – RobPratt
    Jun 30, 2020 at 11:13
  • $\begingroup$ Note that your reformulation relies on the fact that every employee works at least one shift, as enforced by constraint 4. $\endgroup$
    – RobPratt
    Jun 30, 2020 at 12:56
  • $\begingroup$ 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. $\endgroup$
    – Psyndrom Ventura
    Jul 1, 2020 at 12:54
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jul 1, 2020 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.