我正在使用OR工具尝试解决一个类似于护士调度问题的问题，但每个护士(或者在我的情况下，学生(的轮班时间不同。我目前的方法是将偏移划分为最小公分母的块(在我的情况下为5分钟(，并要求：
- 如果学生被安排在当天，他们必须被安排在适当数量的区块
- 这些块必须是连续的
我还设置了学生何时可用/不可用的限制。我下面的当前代码似乎基本上可以工作，但我发现了一些奇怪的情况，没有找到解决方案。例如，在下面的简单示例中，如果我约束Alice在块3和块4期间不可用(从零开始索引(，则即使存在解决方案，求解器也会失败。任何其他约束集(具有可行的解决方案(都可以工作，并符合上述要求。我在定义约束条件时是否做错了什么？有没有更好的方法来实现这一点？我看过这个例子，但我是新手，不太了解发生了什么，所以我希望实现一些更简单的东西。
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)下面的代码包含了Stradivari的建议，并且似乎有效：
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)