1 year ago
#215277
Henrike
Or-tools CP-SAT solver: How can i ensure a mandatory 3 shift break?
I am fairly new to the topic but I have started to implement a shift scheduler using this example: https://developers.google.com/optimization/scheduling/employee_scheduling
Now I want to add the following constrain: after five shifts there needs to be a mandatory break of 3 consecutive shifts before a person can be scheduled again
We have implemented it as shown below, where the logic is that if in the past 6 shifts there is three consecutive shifts where the employee is not on a certain station (no matter the role) I want to enforce that the current engagement can not be staffed. It is important to note that a break of 2 does not count as break but as if the employee had worked.
As an example, if the past shifts looked like this 010011 this employee needs to take a break (0 is not working and 1 is working).
I set up the model as follows:
from ortools.sat.python import cp_model
engagements = {}
model = cp_model.CpModel()
# set up boolean term for each time, emploeyee, station and role
shifts = [1,2,3,4,5,6,7, 8, 9, 10]
employee = ['employee1', 'employee2', 'employee3', 'employee4', 'employee5', 'employee6', 'employee7', 'employee8']
stations = ['station1', 'station2', 'station3', 'station4']
roles = ['senior', 'junior', 'manager']
for y in shifts:
for n in employee:
for d in stations:
for s in roles:
engagements[(y, n, d, s)] = model.NewBoolVar('engagement_y%in{0}d{1}s{2}'.format(n, d, s) % (y))
Next I implemented the constrain, that after five shifts there needs to be at least a 3 shift break for the current station and employee
for n in employee:
for d in stations:
for y in shifts:
# first 5 shifts are fine either way
# past shifts need to be checked
if y > min(shifts)+5:
past_shift_6_4 = model.NewIntVar(0, 1, 'bpast_shift_6_4_y%in{0}d{1}'.format(n, d) % (y))
past_shift_5_3 = model.NewIntVar(0, 1, 'cpast_shift_5_3_y%in{0}d{1}'.format(n, d) % (y))
past_shift_4_2 = model.NewIntVar(0, 1, 'dpast_shift_4_2_y%in{0}d{1}'.format(n, d) % (y))
past_shift_3_1 = model.NewIntVar(0, 1, 'epast_shift_3_1_y%in{0}d{1}'.format(n, d) % (y))
b_6_4 = model.NewBoolVar('b_6_4_y%in{0}d{1}'.format(n, d) % (y))
b_5_3 = model.NewBoolVar('b_5_3_y%in{0}d{1}'.format(n, d) % (y))
b_4_2 = model.NewBoolVar('b_4_2_y%in{0}d{1}'.format(n, d) % (y))
b_3_1 = model.NewBoolVar('b_3_1_y%in{0}d{1}'.format(n, d) % (y))
# set all parameters
if y > min(shifts)+6:
for yp in range(y-4, y-7, -1):
for s in roles:
past_shift_6_4 += engagements[(yp, n, d, s)]
for yp in range(y-3, y-6, -1):
for s in roles:
past_shift_5_3 += engagements[(yp, n, d, s)]
for yp in range(y-2, y-5, -1):
for s in roles:
past_shift_4_2 += engagements[(yp, n, d, s)]
for yp in range(y-1, y-4, -1):
for s in roles:
past_shift_3_1 += engagements[(yp, n, d, s)]
model.Add(past_shift_6_4 == 0).OnlyEnforceIf(b_6_4.Not())
model.Add(past_shift_5_3 == 0).OnlyEnforceIf(b_5_3.Not())
model.Add(past_shift_4_2 == 0).OnlyEnforceIf(b_4_2.Not())
model.Add(past_shift_3_1 == 0).OnlyEnforceIf(b_3_1.Not())
# be true because cooldown not included
model.Add(past_shift_6_4 > 0).OnlyEnforceIf(b_6_4)
model.Add(past_shift_5_3 > 0).OnlyEnforceIf(b_5_3)
model.Add(past_shift_4_2 > 0).OnlyEnforceIf(b_4_2)
model.Add(past_shift_3_1 > 0).OnlyEnforceIf(b_3_1)
final = model.NewBoolVar('final')
model.AddBoolOr([b_6_4.Not(), b_5_3.Not(),b_4_2.Not(),b_3_1.Not(), final])
model.AddImplication(final, b_6_4)
model.AddImplication(final, b_5_3)
model.AddImplication(final, b_4_2)
model.AddImplication(final, b_3_1)
model.Add(engagements[(y, n, d, s)]==0).OnlyEnforceIf(final)
The multiplication was done analog to this: https://github.com/google/or-tools/blob/stable/ortools/sat/doc/boolean_logic.md#python-code-3
I've would expected that final enforces the constraint if all booleans (b_7_5, b_6_4, b_5_3, b_4_2, b_3_1) are true (meaning that the cooldown hasn't taken place in any time window), that's apparently not happening currently.
Any suggestions would be greatly appreciated!
python
or-tools
constraint-programming
cp-sat-solver
0 Answers
Your Answer