Google OR-Tools CP-SAT课程表连续课时约束失效排查

我编写了一个基于Google OR-Tools的学校课程表生成脚本，设置了以下约束：

• 每门科目需达到指定周课时；
• 教师不可同时授课；
• 教师周授课时长不超上限；
• 班级单日单科目课时不超上限；
• 班级单日某科目课时超1则需连续。

当前测试场景为1门科目、1位教师、2个班级（1-A和1-B），但连续课时约束未生效，模型仍会分配非连续课时。核心代码片段与生成的时间表如下：

核心代码片段 #

model = cp_model.CpModel()

# Create decision variables (group-subject-teacher-day-hour)
assignments = {}
for group in all_groups:
     course = group.split('-')[0]
     for subject in all_subjects:
          if subject.course == course:
               for teacher in all_teachers:
                    if subject in teacher.subjects:
                              for d in range(num_days):
                                   for h in range(num_hours):
                                        key = (group, subject.id, teacher.id, d, h)
                                        assignments[key] = model.NewBoolVar(f"g:{group} sub:{subject.id} t:{teacher.name} d:{d} h:{h}")

# Each subject must be taught the specified weekly hours
for group in all_groups:
     course = group.split('-')[0]
     for subject in all_subjects:
          if subject.course == course:
               model.Add(sum(assignments[key] for key in assignments if key[0] == group and key[1] == subject.id) == subject.weekly_hours)

# A teacher cannot teach two classes at the same time
for teacher in all_teachers:
     for d in range(num_days):
          for h in range(num_hours):
               model.AddAtMostOne(assignments[key] for key in assignments if key[2] == teacher.id and key[3] == d and key[4] == h)

# Teachers cannot exceed their maximum assigned weekly hours.
for teacher in all_teachers:
     max_hours = teacher.max_hours_week
     teacher_total_hours = sum(assignments[key] for key in assignments if key[2] == teacher.id)
     model.Add(teacher_total_hours <= max_hours)

# The maximum number of hours per day for each subject and group is limited.
for group in all_groups:
     course = group.split('-')[0]
     for subject in all_subjects:
          if subject.course == course:
               for teacher in all_teachers:
                    if subject in teacher.subjects:
                              for d in range(num_days):
                                   hour_vars = [assignments[key] for key in assignments  if key[0] == group and key[1] == subject.id and key[2] == teacher.id and key[3] == d]
                                   model.Add(sum(hour_vars) <= subject.max_hours_per_day)

# If a subject is taught more than one hour per day in a group, the hours must be consecutive.
for group in all_groups:
     course = group.split('-')[0]
     for subject in all_subjects:
          if subject.course == course:
               for d in range(num_days):
               hour_vars = [assignments[key] for key in assignments if key[0] == group and key[1] == subject.id and key[3] == d]
               if len(hour_vars) >= 2:
                    for h1 in range(len(hour_vars)):
                         for h2 in range(h1 + 1, len(hour_vars)):
                              not_consecutive = model.NewBoolVar(f"not_consecutive_{group}_{subject.id}_{d}_{h1}_{h2}")
                              model.Add(h2 != h1 + 1).OnlyEnforceIf(not_consecutive)
                              model.AddBoolAnd([hour_vars[h1], hour_vars[h2]]).OnlyEnforceIf(not_consecutive)
                              model.Add(not_consecutive == 0)

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

生成的时间表 #

Schedule for 1-A
Hour   | Mon          | Tue          | Wed          | Thu          | Fri         
-------+--------------+--------------+--------------+--------------+-------------
Hour 0 | Maths (John) | -            | -            | Maths (John) | -           
Hour 1 | -            | -            | -            | -            | -           
Hour 2 | -            | Maths (John) | Maths (John) | Maths (John) | Maths (John)
Hour 3 | Maths (John) | Maths (John) | -            | -            | Maths (John)
Hour 4 | -            | -            | Maths (John) | -            | -            

Schedule for 1-B
Hour   | Mon          | Tue          | Wed          | Thu          | Fri         
-------+--------------+--------------+--------------+--------------+-------------
Hour 0 | -            | Maths (John) | Maths (John) | -            | Maths (John)
Hour 1 | Maths (John) | -            | -            | Maths (John) | Maths (John)
Hour 2 | -            | -            | -            | -            | -           
Hour 3 | -            | -            | Maths (John) | -            | -           
Hour 4 | Maths (John) | Maths (John) | -            | Maths (John) | -         

请问该约束失效的原因是什么？

核心问题1：循环缩进错误 #

在连续课时约束的代码块中，hour_vars = [...]这一行没有正确缩进，导致它不在for d in range(num_days):的循环体内。这意味着代码只会处理最后一天的连续约束，其他日期的约束完全没有被添加到模型中，自然无法生效。

核心问题2：约束逻辑错误 #

你当前的约束试图禁止任意两个非连续时段同时被占用，但这个逻辑本身存在严重问题：

• 当单日有3个连续课时（比如h0、h1、h2），h0和h2是非连续的，但它们同时被占用是符合连续要求的，你的约束会错误地禁止这种合法情况；
• 这种逻辑无法覆盖所有非连续场景，比如h0和h3同时被占用的情况，反而会误判合法的连续多课时场景。

修复后的连续约束代码 #

# If a subject is taught more than one hour per day in a group, the hours must be consecutive.
for group in all_groups:
    course = group.split('-')[0]
    for subject in all_subjects:
        if subject.course == course:
            for d in range(num_days):
                # 修正缩进：将hour_vars放在日期循环内
                hour_vars = [assignments[key] for key in assignments if key[0] == group and key[1] == subject.id and key[3] == d]
                # 获取当天该科目总课时数
                daily_total = sum(hour_vars)
                # 当当天课时数>1时，添加连续约束
                for h in range(1, num_hours):
                    # 逻辑：如果当天总课时数>1，那么不能出现"当前时段被占用但前一时段空闲"的情况（除了第一个占用的时段）
                    model.AddImplication(hour_vars[h], hour_vars[h-1]).OnlyEnforceIf(daily_total > 1)

额外优化建议 #

• 原代码中hour_vars的生成可以更高效，直接通过循环小时数构建key，避免遍历整个assignments字典：

  hour_vars = []
  for h in range(num_hours):
      key = (group, subject.id, teacher.id, d, h)
      if key in assignments:
          hour_vars.append(assignments[key])
  

• 原连续约束中的not_consecutive变量完全没必要，逻辑绕弯且容易出错，直接用AddImplication实现的缺口检测逻辑更清晰高效。

内容的提问来源于stack exchange，提问作者Ernesto Hernández