4
$\begingroup$

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the day number and $s \in S$ is the shift (ex: 9AM-12PM) and if the employee is scheduled to work on that day at that shift the variable is 1 otherwise 0.

The set $I = \bigcup J_i$ subsets such that $J_i$ partition the set $I$ and where each $J_i$ represents a subset of priority employees. For example if $i \in [1,2,3]$ then $J_1$ takes precedence over $J_2$ and $J_2$ over $J_3$ in terms of shift scheduling. I want to enforce this condition via the constraints in the optimization instead of the objective function coefficients, but am unsure how to do so. The sets $J_i$ that partition the set $I$ are pre-defined. I'd like to keep this as a linear optimization due to the size of the original problem.

$\endgroup$
4
  • 4
    $\begingroup$ What exactly does it mean that one employee has precedence over another? I'm also a bit puzzled by the definitions of sets I and J_i. One thing you could do is introduce a helper variable $y_i$ to indicate whether employee $i$ is assigned to some shift. Then you could add a constraint like $y_i\leq y_j$ to enforce that employee $i$ cannot be assigned a shift if employee $j$ has not been assigned a shift if $j$ precedes $i$. Similarly, you could add a constraint like $2 y_k \leq y_i+y_j$ to enforce that empl $k$ cannot be assigned shift if employees $i$ and $j$ are unassigned. $\endgroup$ May 4, 2022 at 7:16
  • $\begingroup$ set $I$ is the total number of workers in the optimization, so if it is say 50, then set $J_1$ contains employees who get assigned to shifts first and say that is 30 employees then set $J_2$ is 20 employees who get assigned to shifts after all $J_1$ employees are assigned to shifts. I'm unclear on your proposal for i and j, aren't the $y_i$ variables binary in your example above? $\endgroup$ May 4, 2022 at 13:58
  • $\begingroup$ The prioritization is still a bit unclear. Is an employee in $J_2$ eligible to be assigned to a particular shift on a particular day only after all employees in $J_1$ have been assigned to the same shift on the same day? Only after everyone in $J_1$ has at least one shift on at least one day? Only after everyone in $J_1$ has been assigned to a specified number of shifts in the week? $\endgroup$
    – prubin
    May 4, 2022 at 15:34
  • $\begingroup$ It's the second condition: only after every member in $J_i$ has been assigned to at least one shift per day can you then assign shifts to members in $J_2$ $\endgroup$ May 4, 2022 at 16:32

2 Answers 2

2
$\begingroup$

Another possible model uses a binary variable $Y_{kd}$ to indicate whether all employees in set $J_k$ have been assigned at least one shift on day $d$. The defining constraint is $$ Y_{kd} \le \sum_{s\in S} X_{ids} \quad \forall k, \, \forall i\in {J_k}, \, \forall d\in D.$$ This forces $Y_{kd}=0$ unless each employee $i\in J_k$ has gotten at least one shift on day $d.$ The priority constraint is then enforced by $$X_{ids} \le Y_{kd} \quad \forall k, \, \forall i\in J_{k+1}, \, \forall d\in D,$$ which says that no employee can get a shift unless the next higher priority group were all assigned that day. This introduces fewer binary variables $Y$ and somewhat fewer constraints than does the solution proposed by @PeterD, but it is an empirical question which would solve faster.

$\endgroup$
4
  • $\begingroup$ I like the idea but would the first constraint work? Lets say $|J_k| = 100$, and $|S| = 1$. In that case, $Y_{kd}$ must be $0$, even when a shift is assigned to all employees $i \in J_k$. Should we sum not only over all shifts but also over all $i \in J_k$ in the first constraint? $\endgroup$
    – PeterD
    May 31, 2022 at 19:53
  • 1
    $\begingroup$ Thanks for catching the error (which I've fixed). I think I screwed up transcribing my hand-scrawled solution. No, summing over both shifts and employees won't work, because an employee in cohort $k$ getting skipped will not block the next priority class if another member of cohort $k$ gets two shifts. $\endgroup$
    – prubin
    May 31, 2022 at 20:14
  • $\begingroup$ You are right, that logic errow was the initial mistake in my answer ;) $\endgroup$
    – PeterD
    May 31, 2022 at 20:16
  • $\begingroup$ Clearly we both need more caffeine. :-) $\endgroup$
    – prubin
    May 31, 2022 at 20:17
1
$\begingroup$

You state that only after every member in $J_i$ (I assume you mean $J_1$ in this specific example) has been assigned to at least one shift per day, you can assign shifts to members in $J_2$. To do that you can add the following constraint which is similar to the idea of @Joris Kinable:

$$Y_{id} \cdot M \geq \sum_{s\in S} X_{ids} \quad \forall i\in I, d \in D $$

$$Y_{id} \geq Y_{jd} \quad \forall k, i\in J_k, j\in J_{k+1}, d \in D $$ $$Y_{id} \in \{0,1\} \quad \forall i \in I, d\in D$$

$Y_{id}$ is a binary help variable which is $1$ if employee $i$ is scheduled at least once on day $d$ (see the first constraint). $M$ is a sufficiently large number, in your case that could be the cardinality of $S$, i.e $|S|$. The second constraint makes sure that if any employee $j \in J_{k+1}$ is scheduled on day $d$, then all employees $i \in J_k$ also need to be scheduled on that day.

$\endgroup$
3
  • $\begingroup$ I don't believe this works. The constraint says that on each day $d$ the number of employees from $J_2$ who are assigned a shift cannot exceed the number of employees from $J_1$ who are assigned a shift. So if three of five employees from $J_1$ are scheduled, then you can schedule up to three from $J_2$, which contradicts mathcomp guy's response to my comment above. Also, if you schedule five of five employees from $J_1$, you can only schedule at most five from $J_2$, even though $J_2$ might contain more than five employees and all $J_1$ employees have been scheduled. $\endgroup$
    – prubin
    May 30, 2022 at 21:48
  • $\begingroup$ @prubin Thanks for the remark. Is that really the case? I am not summing over employees but over shifts. So if there is any employee $j \in J_2$ scheduled on a day, then all employees $i \in J_1$ also need to be scheduled. A problem would arise if an employee $j \in J_2$ is assigned to multiple shifts, because then every employee $i \in J_1$ also needs to be scheduled multiple times. I adapted my answer for that case. $\endgroup$
    – PeterD
    May 31, 2022 at 7:08
  • $\begingroup$ You're right, I misread the summation. $\endgroup$
    – prubin
    May 31, 2022 at 15:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.