3

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!

Henrike
  • 31
  • 4
  • 2
    Without really looking at your model, i just want to mention, that i would tackle this always (as long as it's about feasibility: no "soft-constraint") by using a [DFA](https://developers.google.com/optimization/reference/python/sat/python/cp_model#addautomaton). This is imho much more generic, easier to understand and has a strong theoretical core in regards to propagation. – sascha Feb 23 '22 at 11:58
  • Hey, thanks for your comment! Do you have an example of this? I dont quite understand how to apply this to my problem. – Henrike Feb 24 '22 at 07:37
  • 1
    You might skim over [Gecode Docs: 4.4.13](https://www.gecode.org/doc-latest/MPG.pdf), some basic automata/cp papers like [Toward an automaton Constraint for Local Search](https://arxiv.org/pdf/0910.1266.pdf) or [Solving Nurse Rostering Problems Using Soft Global Constraints](https://hal.archives-ouvertes.fr/hal-01015106/document). I guess, these approaches should feel natural when someone touched DFAs before (e.g. every computer scientist). When the concept is understood, abstraction is won and different solvers work on the same description (or-tools, gecode, ...). – sascha Feb 24 '22 at 10:42
  • 1
    One more good overview: [Flexible Optimization: Nurse Scheduling with Constraint Programming and Automata](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.441&rep=rep1&type=pdf) – sascha Feb 24 '22 at 12:17
  • 1
    Thanks! This really helped me. Once I have figured out how to finally implement this I will post it! – Henrike Feb 28 '22 at 07:50
  • @Henrike have you been able to solve it? – Jan Koekepan May 09 '22 at 14:24

0 Answers0