4

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.

mathcomp guy
  • 275
  • 1
  • 6
  • 4
    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. – Joris Kinable May 04 '22 at 07:16
  • 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? – mathcomp guy May 04 '22 at 13:58
  • 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? – prubin May 04 '22 at 15:34
  • 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$ – mathcomp guy May 04 '22 at 16:32

2 Answers2

2

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 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? – PeterD May 31 '22 at 19:53
  • 1
    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. – prubin May 31 '22 at 20:14
  • You are right, that logic errow was the initial mistake in my answer ;) – PeterD May 31 '22 at 20:16
  • Clearly we both need more caffeine. :-) – prubin May 31 '22 at 20:17
1

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.

PeterD
  • 1,501
  • 4
  • 16
  • 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. – prubin May 30 '22 at 21:48
  • @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. – PeterD May 31 '22 at 07:08
  • You're right, I misread the summation. – prubin May 31 '22 at 15:18