I'm working on a scheduling/rostering problem. In this scenario the shifts are predefined with a starting and ending date and time.
The problem basically assigns people to shifts with a binary variable $x_{ij} = 1$ if person $i$ is assigned to shift $j$ and $0$ otherwise.
In this problem there are especial shifts that represent the rest time. This shifts also have a start and end date and time.
The problem already takes care of simultaneous shifts and rest time between shifts, so those constraints are already working.
However, I want to restrict the amount of "working" shifts before a "rest" shift.
It should be something like: at most 4 working shifts before a rest shift.
How would I model those constraints?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Shifts can overlap each other chronologically? (I'm not asking whether workers can work overlapping shifts, just whether the shifts would overlap if drawn on a time line.) Can we assume that every worker is assigned to either a working shift or a resting shift at all times? Last, are all working shifts of the same duration? $\endgroup$– prubin ♦Mar 9 at 21:09
-
$\begingroup$ @prubin, 1. Yes, shifts can overlap (and will) if drawned in a timeline. 2. No, workers not necessarily would be assigned to a working or rest shift all time. 3. Yes, al working shifts have a duration of 9 hours. $\endgroup$– Daniel BaqueroMar 9 at 21:33
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
To model the constraint that limits the number of working shifts before a rest shift, you can introduce an additional binary variable to represent whether a person is on rest or not, and then use this variable to enforce the constraint.
Let $y_i$ be a binary variable that is equal to 1 if person $i$ is on rest and 0 otherwise. Then, for each person $i$ and each shift $j$, we can introduce a binary variable $w_{ij}$ that is equal to 1 if person $i$ is working on shift $j$ and 0 otherwise.
To enforce the constraint that limits the number of working shifts before a rest shift, we can use a set of constraints that ensure that if person $i$ is working on shift $j$, then they must also have worked on at most 3 other shifts in the previous 4 shifts. This can be modeled as follows:
$$ \sum_{k=j-3}^{j-1} w_{ik} + w_{ij} \leq 4 - 4 y_i \quad \forall i,j $$
This constraint ensures that if person $i$ is on rest (i.e., $y_i = 1$), then they can work on up to 4 consecutive shifts before their rest shift. If person $i$ is not on rest (i.e., $y_i = 0$), then they must have worked on at most 3 other shifts in the past 4 shifts before working on shift $j$, in order to satisfy the constraint.
Note that this constraint assumes that there are no gaps between shifts. If there are gaps between shifts, then you may need to modify the constraint to take this into account. Additionally, you may need to modify the constraint to handle cases where the rest shift occurs at the beginning or end of the scheduling period.
-
$\begingroup$ This also assumes that there are no overlapping shifts. In this particular case, the last 4 shifts may overlap with the current shift. As there are constraints to prevent assignment to overlapping shifts the problem would be infeasible. $\endgroup$ Mar 20 at 15:33
$\begingroup$
$\endgroup$
If aim is to restrict non consecutive shifts then
$ \sum_{j\lt k}x_{ij} \le 3+y_{i,k} \\\forall k\in S_i$
where $S_i$ is set of designated shift time for worker $i$ and shift indicator is the binary $y$.
If consecutive shift then
$\sum_{j\lt k}^{j-3} x_{i,k} \le 3 +y_{i,k} $
You may also have $x_{ik}+y_{ik} \le 1$
