我正在使用 OR-Tools 尝试解决类似于“护士调度问题”的问题，但每个护士（或者在我的例子中，学生）的轮班长度不同。我目前的方法是将轮班划分为最小公分母的区块（在我的例子中为 5 分钟），并要求：
如果学生当天被安排，则必须为他们安排适当数量的区块，但我对此很陌生，不太明白发生了什么，所以希望实现一些更简单的东西。
from ortools.sat.python import cp_model
#assign student[0] to be a placeholder, stands for "no students during this time"
student_names = ['none','Alice']
#number of sessions per student; i.e. Alice needs 1 session
student_sessions = [0,1]
#how many 5-minute blocks for each student's sessions; i.e. Alice's sessions are 3x5 minutes long
student_blocks = [0,3]
#constraints, in the form (student,day,block); i.e. Alice can't be scheduled in block 3 on day 0
constraints = [(1,0,3)]
#define the length of the day
num_blocks = 6
#define the number of days in the week
num_days = 1
num_students = len(student_sessions)
print('Scheduling',num_students-1,'students') #recall that student[0] is just a placeholder
students = range(num_students)
blocks = range(num_blocks)
days = range(num_days)
#create the model
model = cp_model.CpModel()
#create the primary variable 'slots', a list of booleans with coordinates given by student, day, block
slots = {}
for s in students:
for d in days:
for b in blocks:
slots[(s,d,b)] = model.NewBoolVar('block_s%id%ib%i' % (s,d,b))
#no more than 1 student per block
for d in days:
for b in blocks:
model.Add(sum(slots[(s,d,b)] for s in students)==1)
#require the total number of blocks per student = # sessions x blocks per session
for s in students[1:]: #we always skip over constraints for student[0]; they can fill in everything else
total = 0
for d in days:
for b in blocks:
total += slots[(s,d,b)]
model.Add(total == int(student_sessions[s]*student_blocks[s]))
#each day, student should either have no blocks, or a number of blocks equaling their session length
for d in days:
for s in students[1:]:
blocked = model.NewBoolVar('blocking')
noblock = model.NewBoolVar('noblock')
model.Add(sum(slots[(s,d,b)] for b in blocks)==student_blocks[s]).OnlyEnforceIf(blocked)
model.Add(sum(slots[(s,d,b)] for b in blocks)==0).OnlyEnforceIf(noblock)
model.AddBoolOr([blocked,noblock])
# require session continuity, i.e. all a students blocks should be sequential, not spread out over a day
for d in days:
for s in students[1:]:
for b in blocks[:-(student_blocks[s])]:
cont = model.NewBoolVar('cont')
startBlock = model.NewBoolVar('startBlock')
model.Add(sum([slots[(s,d,b)]])==0).OnlyEnforceIf(startBlock)
model.Add(sum(slots[(s,d,b+i)] for i in range(student_blocks[s]))==student_blocks[s]).OnlyEnforceIf(cont)
model.AddBoolXOr([startBlock,cont])
for ct in constraints:
model.Add(slots[ct]==0)
solver = cp_model.CpSolver()
solver.Solve(model)
for d in days:
print('Day',d)
for b in blocks:
for s in students:
if solver.Value(slots[(s,d,b)])==1:
print(student_names[s],'in block',b)
from ortools.sat.python import cp_model
def negated_bounded_span(works, start, length):
"""Filters an isolated sub-sequence of variables assined to True.
Extract the span of Boolean variables [start, start + length), negate them,
and if there is variables to the left/right of this span, surround the span by
them in non negated form.
Args:
works: a list of variables to extract the span from.
start: the start to the span.
length: the length of the span.
Returns:
a list of variables which conjunction will be false if the sub-list is
assigned to True, and correctly bounded by variables assigned to False,
or by the start or end of works.
"""
sequence = []
# Left border (start of works, or works[start - 1])
if start > 0:
sequence.append(works[start - 1])
for i in range(length):
sequence.append(works[start + i].Not())
# Right border (end of works or works[start + length])
if start + length < len(works):
sequence.append(works[start + length])
return sequence
#assign student[0] to be a placeholder, stands for "no students during this time"
student_names = ['none','Alice']
#number of sessions per student; i.e. Alice needs 1 session
student_sessions = [0,1]
#how many 5-minute blocks for each student's sessions; i.e. Alice's sessions are 3x5 minutes long
student_blocks = [0,3]
#constraints, in the form (student,day,block); i.e. Alice can't be scheduled in block 3 on day 0
constraints = [(1,0,5)]
#define the length of the day
num_blocks = 6
#define the number of days in the week
num_days = 1
num_students = len(student_sessions)
print('Scheduling',num_students-1,'students') #recall that student[0] is just a placeholder
students = range(num_students)
blocks = range(num_blocks)
days = range(num_days)
#create the model
model = cp_model.CpModel()
#create the primary variable 'slots', a list of booleans with coordinates given by student, day, block
slots = {}
for s in students:
for d in days:
for b in blocks:
slots[(s,d,b)] = model.NewBoolVar('block_s%id%ib%i' % (s,d,b))
#no more than 1 student per block
for d in days:
for b in blocks:
model.Add(sum(slots[(s,d,b)] for s in students)==1)
#require the total number of blocks per student = # sessions x blocks per session
for s in students[1:]: #we always skip over constraints for student[0]; they can fill in everything else
total = 0
for d in days:
for b in blocks:
total += slots[(s,d,b)]
model.Add(total == int(student_sessions[s]*student_blocks[s]))
#each day, student should either have no blocks, or a number of blocks equaling their session length
for d in days:
for s in students[1:]:
blocked = model.NewBoolVar('blocking')
noblock = model.NewBoolVar('noblock')
model.Add(sum(slots[(s,d,b)] for b in blocks)==student_blocks[s]).OnlyEnforceIf(blocked)
model.Add(sum(slots[(s,d,b)] for b in blocks)==0).OnlyEnforceIf(noblock)
model.AddBoolOr([blocked,noblock])
#require sessions be the correct length
for s in students[1:]:
for d in days:
sts = [slots[(s,d,b)] for b in blocks]
for length in range(1, student_blocks[s]):
for start in range(len(sts) - length + 1):
model.AddBoolOr(negated_bounded_span(sts, start, length))
for ct in constraints:
model.Add(slots[ct]==0)
solver = cp_model.CpSolver()
solver.Solve(model)
for d in days:
print('Day',d)
for b in blocks:
for s in students:
if solver.Value(slots[(s,d,b)])==1:
print(student_names[s],'in block',b)