基于OR-Tools CP-SAT的学校排课课间空挡软约束实现求助

核心逻辑锚定 #

首先明确空挡的统计边界：仅统计同一工作日内、同一授课主体（教师/固定班/走班小组）的排课序列中，被前后两个上课时隙夹在中间的空闲教学时隙；固定午休、大课间这类预设的非教学间隔不计入空挡，避免错误统计正常休息时间。

松弛变量的设计逻辑 #

因为最小化空挡是软约束，不需要像硬约束那样通过松弛变量放宽约束边界，而是通过可计数的惩罚变量，让模型在满足所有硬约束的前提下，主动选择空挡总数最少的排课方案，不需要设计复杂的带优先级的硬松弛项：

• 逐点生成空挡判定的布尔辅助变量，替代枚举所有课对的复杂计算：针对每个需要统计的主体、每个工作日、每个可用于排课的教学时隙，新建一个布尔变量is_gap，取值为1代表这个时隙属于空挡，取值为0代表不属于。
• 给is_gap绑定判定约束：
  • 如果当前时隙主体没有排课，且当前时隙往前追溯到当日首个排课时隙的区间内、以及往后追溯到当日日终的区间内，分别存在至少一个已排的课，就强制is_gap = 1
  • 其他场景下，强制is_gap = 0
• 把所有is_gap变量乘以设置好的惩罚权重，统一加入模型的最小化目标函数。权重可以根据实际排课需求调整：单空挡惩罚值设置过高，会挤占其他排课目标的求解空间；设置过低则无法有效引导模型减少空挡。

易踩的实现偏差 #

• 空挡统计不要跨工作日计算，所有判定严格限定在单日的排课序列内
• 对横跨午休的长间隔时隙，可以单独标记为“固定非教学间隙”，直接排除在空挡判定的约束范围外，避免模型为了消空挡强制把午休前后的课连排
• 如果存在不同长度的空挡（比如1个课时的短空挡、2个课时的长空挡），可以给不同类型的空挡设置差异化惩罚，比如长空挡的惩罚更高，更贴近实际排课的需求

核心代码片段参考 #

# 前置变量：has_lecture[t][d][s] 为已定义的排课布尔变量，1代表主体t在d日s时段有课
# 针对单个空挡位置定义判定变量
is_gap = model.NewBoolVar(f"gap_{t}_{d}_{s}")

# 绑定空挡判定逻辑：当前位置无课，且前后区间都存在已排课程时，is_gap取值为1
model.Add(has_lecture[t][d][s] == 0).OnlyEnforceIf(is_gap)
model.Add(sum(has_lecture[t][d][:s]) >= 1).OnlyEnforceIf(is_gap)
model.Add(sum(has_lecture[t][d][s+1:]) >= 1).OnlyEnforceIf(is_gap)

# 目标函数整合硬约束惩罚与空挡惩罚项
model.Minimize(
  total_hard_constraint_violation_penalty + gap_weight * sum(all_is_gap_var)
)

内容的提问来源于stack exchange，提问作者Tarik Ouhamou