# crew scheduling problem with shift priority hard constraints

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.

• 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. Commented May 4, 2022 at 7: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? Commented May 4, 2022 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
Commented May 4, 2022 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$ Commented May 4, 2022 at 16:32

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.

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

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.

• 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
Commented May 30, 2022 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. Commented May 31, 2022 at 7:08
• You're right, I misread the summation.
– prubin
Commented May 31, 2022 at 15:18