or-tools Employee Scheduling sequential allocations staff groups

Question

Using standard/simple nursing example: https://developers.google.com/optimization/scheduling/employee_scheduling

I'm trying to enforce nurses from a particular group/team to be allocated days consecutively. As below, nurses 1-9 split into "groups". If nurse 9 is allocated first, then other members from group (4 and 7) should be allocated to following days.

Thinking I can possibly achieve this by counting the amount of times members from a group are allocated one day after another, but am unable to count when this occurs, i.e. both day_i and day_i+1 are allocated to nurses from same group.

groups = [[3,7,8],[1,6],[5],[4,9,7]] #nurses 3,7,8 are in same group
...
for g in groups:
    for d1, d2 in zip(all_days[:-1],all_days[1:]):
        d1_alloc = sum(shifts[(n, d1, s)] for n in g)
        d2_alloc = sum(shifts[(n, d2, s)] for n in g)
        # ??? how to say only count when both sums = 1/true ???
        # for a group of 3, i.e. [3,7,8] this should occur twice within period

Full Code:

from ortools.sat.python import cp_model

all_days = range(1,10)
all_nurses = range(1,10)
groups = [[3,7,8],[1,6],[5],[4,9,7]] #nurses 3,7,8 are in same group
s=1 #1 shift only

model = cp_model.CpModel()

shifts = {}
for d in all_days:
    for n in all_nurses:
        shifts[(n, d, s)] = model.NewBoolVar('shift_n%sd%is%i' % (n, d, s))
            
# one nurse per shift
for d in all_days:
    model.Add(sum(shifts[(n, d, s)] for n in all_nurses) == 1)
               
# everyone works a shift
for n in all_nurses:
    model.Add(sum(shifts[(n, d, s)] for d in all_days) == 1)
 
# nurses within group should be allocated days one after another
# order of groups is not important - last group [4,9,7] could be allocated firts
# order within groups is not important - can be 7,4,9
    
for g in groups:
    for d1, d2 in zip(all_days[:-1],all_days[1:]):
        d1_alloc = sum(shifts[(n, d1, s)] for n in g)
        d2_alloc = sum(shifts[(n, d2, s)] for n in g)
        # ??? how to say only count when both sums 1/true ???
        # for a group of 3, i.e. [3,7,8] this should occur twice within period


solver = cp_model.CpSolver()
solver.Solve(model)

for d in all_days:
    for n in all_nurses:
        if solver.Value(shifts[(n, d, s)]) == 1:
            print('Day: '+str(d)+' = Nurse '+str(n))

EDIT: The following logic can be used to achieve this

for group in groups:     
    for n1, n2 in zip(group[:-1],group[1:]):
        for d in all_days[:-1]:

            model.AddBoolOr([shifts[n1, d, 1],shifts[n2, d+1, 1].Not()])
            model.AddBoolOr([shifts[n1, d, 1].Not(),shifts[n2, d+1, 1]])

This solution is restrictive - Allocations must follow the same sequence as the group is listed. Group [3,7,8] will always be 3,7,8 but not 7,3,8 or 8,3,7 for example... which would also be fine.

It is also necessary to ensure that Day 1 is allocated to someone from the start of a group. model.Add(sum(shifts[(n, 1, s)] for n in [3,1,5,4]) ==1)

If there are only groups of up to 2 members, the following will allow either order. For group [3,7] for example... 3,7 or 7,3.

for group in groups:     
    for n1, n2 in zip(group[:-1],group[1:]):
        
        #Day1
        model.AddImplication(shifts[n1, 1, 1],shifts[n2, 2, 1])
        model.AddImplication(shifts[n2, 1, 1],shifts[n1, 2, 1])
        
        #Day2 + must check preceding day to avoid circular/repeated allocations
        for d in all_days[1:-1]:
            
          model.AddImplication(shifts[n1, d, 1],shifts[n2, d+1, 1]).OnlyEnforceIf(shifts[n2, d-1, 1].Not())
          model.AddImplication(shifts[n2, d, 1],shifts[n1, d+1, 1]).OnlyEnforceIf(shifts[n1, d-1, 1].Not())

EDIT 2: The following can be used to solve for groups of any size...

for g in groups:
    
    for i in range(0,len(g)):
        #1 cycle for every group order [3,7,2], [7,2,3],[2,3,7]

        for d in all_days[:-(len(g)-1)]:
            
            conditions_met = [shifts[g[0], d, 1]] #n1 allocated today
            if d > 1:
                #ensure group members not allocated previous day
                for n in g:
                    conditions_met.append(shifts[n, d-1, 1].Not())
            
            #apply rules for next x days - depending on size of group
            for day in range(d+1,d+len(g)):
                or_cond = []
                for n in g[1:]:
                    or_cond.append(shifts[n,day,1])
                model.AddBoolOr(or_cond).OnlyEnforceIf(conditions_met)

        x = g.pop(0)
        g.append(x)

Answer 1

For more complex constraints, I suggest looking at this shift scheduling example

In particular in contains min and max sequence constraints.