背景教培机构的排课问题是一个经典的约束满足问题CSP。一个中型机构可能有50个老师、200个班级、10间教室、5个时间段需要在满足各种约束条件下生成一份无冲突的课表。我们最初用回溯算法实现了一版排课引擎在小规模数据下运行良好。但当机构学员超过500人时排课耗时从几秒飙升到几分钟甚至超时。今天分享我们从回溯算法迁移到Google OR-Tools约束求解器的过程和踩坑经验。一、回溯算法的瓶颈最初的排课引擎使用经典的回溯加剪枝策略。核心数据结构是一个三维矩阵// timeslot[teacher][class][room] true/false// 表示老师t在教室r给班级c上课是否可行class ScheduleBacktracker:def __init__(self, teachers, classes, rooms, timeslots):self.teachers teachersself.classes classesself.rooms roomsself.timeslots timeslotsself.assignment {} # {class_id: (teacher_id, room_id, timeslot_id)}def is_valid(self, class_id, teacher_id, room_id, timeslot_id):# 检查教师时间冲突for cid, (tid, rid, ts) in self.assignment.items():if tid teacher_id and ts timeslot_id:return False# 检查教室时间冲突if rid room_id and ts timeslot_id:return False# 检查教师跨校区通勤时间teacher self.teachers[teacher_id]for cid, (tid, rid, ts) in self.assignment.items():if tid teacher_id:time_diff abs(ts - timeslot_id)if time_diff 1:room1 self.rooms[rid]room2 self.rooms[room_id]if room1.campus ! room2.campus:return False # 相邻时段不同校区不可行return Truedef backtrack(self, class_ids):if not class_ids:return Trueclass_id class_ids[0]for teacher_id in self.teachers:for room_id in self.rooms:for timeslot_id in self.timeslots:if self.is_valid(class_id, teacher_id, room_id, timeslot_id):self.assignment[class_id] (teacher_id, room_id, timeslot_id)if self.backtrack(class_ids[1:]):return Truedel self.assignment[class_id]return False这个实现在50个班级以内时大约2到3秒出结果。但到了200个班级时搜索空间爆炸运行10分钟也排不完。即使加了MRV最小剩余值和LCV最少约束值启发式策略改善也有限。二、迁移到OR-Tools CP-SAT求解器Google OR-Tools的CP-SAT求解器是我们找到的最佳替代方案。它内部使用了高效的约束传播和Lazy Clause Generation技术处理大规模CSP问题的能力远超手写回溯。核心思路是把排课问题建模为布尔变量矩阵from ortools.sat.python import cp_modelclass ScheduleOptimizer:def __init__(self, teachers, classes, rooms, timeslots):self.model cp_model.CpModel()self.teachers teachersself.classes classesself.rooms roomsself.timeslots timeslotsself.vars {} # {class_id: {teacher_id: {room_id: {timeslot_id: BoolVar}}}}def build_model(self):# 创建布尔变量for c in self.classes:self.vars[c.id] {}for t in c.available_teachers:self.vars[c.id][t] {}for r in self.rooms:if r.type c.required_room_type:self.vars[c.id][t][r] {}for ts in c.available_timeslots:self.vars[c.id][t][r][ts] self.model.NewBoolVar(fc{c.id}_t{t}_r{r.id}_ts{ts})# 约束1每个班级恰好分配一个老师教室时间段for c in self.classes:all_vars []for t in self.vars[c.id]:for r in self.vars[c.id][t]:for ts in self.vars[c.id][t][r]:all_vars.append(self.vars[c.id][t][r][ts])self.model.AddExactlyOne(all_vars)# 约束2同一老师同一时间段只能上一门课for t in self.teachers:for ts in self.timeslots:conflict_vars []for c in self.classes:if t.id in self.vars.get(c.id, {}) and ts.id in self.vars[c.id][t.id].get(next(iter(self.vars[c.id][t.id])), {}):for r in self.vars[c.id][t.id]:if ts in self.vars[c.id][t.id][r]:conflict_vars.append(self.vars[c.id][t.id][r][ts])if len(conflict_vars) 1:self.model.AddAtMostOne(conflict_vars)# 约束3同一教室同一时间段只能有一门课for r in self.rooms:for ts in self.timeslots:conflict_vars []for c in self.classes:if c.id in self.vars:for t in self.vars[c.id]:if r.id in self.vars[c.id][t] and ts.id in self.vars[c.id][t][r.id]:conflict_vars.append(self.vars[c.id][t][r.id][ts])if len(conflict_vars) 1:self.model.AddAtMostOne(conflict_vars)# 约束4教师跨校区通勤约束for t in self.teachers:for ts_idx in range(len(self.timeslots) - 1):ts1 self.timeslots[ts_idx]ts2 self.timeslots[ts_idx 1]for r1 in self.rooms:for r2 in self.rooms:if r1.campus ! r2.campus:for c1 in self.classes:for c2 in self.classes:if c1.id ! c2.id and t.id in self.vars.get(c1.id, {}) and t.id in self.vars.get(c2.id, {}):v1 self.vars[c1.id][t.id].get(r1.id, {}).get(ts1.id)v2 self.vars[c2.id][t.id].get(r2.id, {}).get(ts2.id)if v1 and v2:self.model.Add(v1 v2 1)迁移过程中最大的坑是变量数量爆炸。200个班级乘以50个老师乘以10间教室乘以5个时间段布尔变量数量达到50万个。OR-Tools虽然能处理这个规模但内存占用很高。解决方案是预处理阶段做激进的变量剪枝。对于每个班级只保留真正可用的老师、教室和时间段组合把不可能的组合直接从变量空间里剔除。实际操作后变量数量降到了5万左右求解时间从超时降到8到12秒。三、优化目标与软约束排课不只是找到一份可行解还要找到一份好的课表。比如老师不希望一天跑三个校区教室不希望频繁切换热门时间段应该优先分给大班课。这些是软约束不能硬性排除但可以设为优化目标。OR-Tools支持通过AddHint和Minimize来实现# 目标函数最小化教师跨校区次数cross_campus_count []for t in self.teachers:for ts_idx in range(len(self.timeslots) - 1):ts1 self.timeslots[ts_idx]ts2 self.timeslots[ts_idx 1]for r1 in self.rooms:for r2 in self.rooms:if r1.campus ! r2.campus:for c1 in self.classes:for c2 in self.classes:if c1.id ! c2.id:v1 self.vars[c1.id][t.id].get(r1.id, {}).get(ts1.id)v2 self.vars[c2.id][t.id].get(r2.id, {}).get(ts2.id)if v1 and v2:cross_campus self.model.NewBoolVar(fcc_{t.id}_{ts_idx})self.model.Add(v1 v2 1 cross_campus)cross_campus_count.append(cross_campus)self.model.Minimize(sum(cross_campus_count))加入优化目标后求解时间增加到15到20秒但生成的课表质量明显提升。教师跨校区次数平均减少了60%。四、总结从回溯算法迁移到OR-Tools的核心收获1. 约束满足问题不要自己写求解器CP-SAT已经做了大量优化性能远超手写方案。2. 变量预处理比求解器优化更重要减少变量数量是最有效的性能提升手段。3. 软约束和优化目标的设计需要跟业务方反复对齐不同机构对好课表的定义不同。4. 求解时间控制在15秒以内是用户可接受的边界超过这个时间需要加进度提示。
