1 year ago

#215277

test-img

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

Accepted video resources