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)
For more complex constraints, I suggest looking at this shift scheduling example
In particular in contains min and max sequence constraints.