I am trying to build a staff scheduling model that avoids split shifts (3+ hours between jobs), but I am having trouble working out a good constraint to capture this.
The decision variables are $x_{[i,j]}$, subject to a number of constraints, and $x_{[i,j]}= 1$ when staff member $i$ is assigned to job $j$.
So far, I have implemented a callback to check the solution to see if any staff member has been assigned a set of jobs that gives them a split shift, and then include a lazy constraint that says that they can only take one of the two jobs that cause the split shift.
There are two problems I can see with this:
it doesn't cover the case where there are two early jobs and one late job, if we say we can only do one of the two jobs that are causing the split shift, then, if it chooses the late one, we still have a split shift between the earliest job and the late job. of course, this would be captured in subsequent callbacks, but it feels wrong to do it that way.
it doesn't allow for split shifts to be broken by adding an extra job in between. If we have two jobs that are causing a split shift, we can fix that split shift by inserting a job in between those two jobs, and then we don't have to choose between the two.
One idea I have been toying with is this:
say, $x_{[i,\alpha]}$ and $x_{[i,\omega]}$ are causing the split shift. In the callback I add a constraint that looks like this:
$x_{[i,\alpha]} + x_{[i,\omega]} + \displaystyle\sum_{j \in A} x_{[i,j]} \geq 3x_{[i,\alpha]}x_{[i,\omega]}$,
where $A$ is the set of all jobs that lie in between job $\alpha$ and job $\omega$.
Here, we are saying that if we are including BOTH $x_{[i,\alpha]}$ and $x_{[i,\omega]}$, then there must be at least one job in between them (I think, hehe).
Does that seem like it would work? It still allows the solver to choose one or the other in the next iteration if it wants, but you still end up with the problem that if there are two early jobs and one late job, that you have to wait til the next callback to add the constraint for the earliest and late job. But maybe this is unavoidable?
One thing I think this constraint doesn't handle is when $A=\emptyset$. But I suppose it is still saying "you can't choose both of these jobs at the same time" because $x_{[i,\alpha]} + x_{[i,\omega]}$ can never equal 3 in that case?
Is there a standard way of handling this type of constraint? I would imagine it would come up pretty often in a lot of staff scheduling problems..
Your proposed constraint is nonlinear. Instead, the following linear constraint captures what you want: $$x_{[i,\alpha]} + x_{[i,\omega]} -1\le \displaystyle\sum_{j \in A} x_{[i,j]}.$$ If both variables on the left are 1, then at least one variable in the sum must be 1.
Also, if $A$ is empty, then those two variables did not cause a split shift.