排课算法迭代分析
编写日期：2026-07-06 当前版本：v1.0.0 当前算法：五阶段贪心 + 单次置换回溯 + 可选禁忌搜索优化层 实施状态：禁忌搜索已于 v2.21.0 实现并集成
一、当前算法现状
1.1 算法结构
排课核心逻辑位于 server/src/services/arrange/auto-arrange.js，采用五阶段贪心 + 单次置换回溯：
| 阶段 | 处理对象 | 策略 |
|---|---|---|
| 阶段 1 | 有学院/层次意向的教师 | 严格按意向分配，拿第一本教材 |
| 阶段 2 | 无指定意向的教师 | 按课时容量拿第一本教材 |
| 阶段 3 | 所有教师 | 追加同教材班级（不增加教材数） |
| 阶段 4 | 所有教师 | 拿第二本教材 |
| 阶段 5 | 兜底 | 评分 + 负载均衡分配 |
| 置换 | 未分配班级 | 单轮置换，不递归 |
1.2 算法优势
- 速度快：单次遍历，复杂度 O(classes × teachers)，典型数据量下毫秒级完成
- 可解释性强：五阶段逻辑清晰，排课结果容易向用户解释
- 教材内聚有保障：阶段 1-3 的教材分组策略天然保证了"先拿完一本教材再拿下一本"
- 意向约束严格：阶段 1 对意向教师做硬过滤，不会违反业务规则
1.3 算法局限
- 无全局回溯：一旦某教师在前期被分配，后续阶段无法撤回，即使全局有更优分配
- 阶段顺序敏感：先处理的课程"抢走"优质教师，后处理的课程只能捡剩余
- 单次置换能力有限：
trySwapUnassigned只做一步交换，无法完成 A→B→C 的链式调整 - 评分是局部的：
calcMatchScore在选教师时只看当前这一对的得分，不考虑对其他分配的影响
二、候选方案：禁忌搜索
2.1 核心思路
不替换现有算法，而是在其基础上追加优化层：
现有五阶段贪心（构造初始解）
↓
禁忌搜索（迭代优化初始解）
↓
输出最终结果贪心算法负责快速生成一个可行解，禁忌搜索在这个解的基础上反复"微调"，尝试找到更优的分配方案。
2.2 关键设计
解的表示
一个解就是 classId → teacherId 的映射表，与当前 assigned 数组结构一致。目标函数是所有已分配的 calcMatchScore 总和，减去未分配班级的惩罚。
邻域移动算子（三种）
| 移动类型 | 操作 | 说明 |
|---|---|---|
| Insert | 将未分配班级插入某教师 | 可能挤占容量，需检查约束 |
| Shift | 将某教师的班级移给另一教师 | 释放源教师容量，接收教师需有空间 |
| Swap | 两个教师交换各自的一个班级 | 双方容量和约束都需满足 |
每次移动后检查硬约束（容量上限、教材上限 MAX_TEXTBOOKS_PER_TEACHER、学院/层次意向），不可行的移动直接跳过。
禁忌表
记录最近 N 轮被移动的 (classId, teacherId) 对，防止算法在局部来回震荡。禁忌期限（tenure）建议设为 7-15 轮。
接受准则
每轮从所有邻居中选得分最高的非禁忌移动。如果被禁忌的移动能产生比历史最优更好的解（aspiration criterion），则忽略禁忌。
终止条件
- 达到最大迭代次数（建议 200-500 轮）
- 或连续 N 轮无改进（建议 50 轮）
- 或超过时间预算（单课程 10 秒，与批量 5 分钟超时兼容）
2.3 不变的部分
以下模块完全不改，无论是否引入禁忌搜索：
| 模块 | 文件 | 说明 |
|---|---|---|
| 数据查询 | arrange/queries.js | 教师/班级加载、教材推导、匹配谓词 |
| 输入校验 | arrange/validate.js | 课时设置校验 |
| 批量编排 | arrange/batch.js | 课程优先级排序、跨课程累计 |
| 并发控制 | auto-arrange.js 锁部分 | arrangeLocks、batchLocks |
| 服务入口 | teaching-arrange.service.js | re-export |
| HTTP 接口 | teaching-arrange.controller.js | 所有端点、参数、审计日志 |
| 配置常量 | constants/index.js | 权重参数继续作为目标函数权重 |
| 数据库写入 | auto-arrange.js 事务部分 | 二次校验、降级跳过 |
| 结果构建 | auto-arrange.js 统计部分 | buildResult、diagnoseFailure、calcAllMatchRates |
| 前端 | 全部 | 接口入参出参不变，零改动 |
2.4 实际改动（v2.21.0 已实施）
| 组件 | 改动方式 |
|---|---|
| 五阶段分配（Phase 1-5） | 保留不动，作为初始解构造 |
trySwapUnassigned() | 保留，禁忌搜索在其之后追加运行 |
calcMatchScore() | 复用为禁忌搜索全局目标函数 |
tabu-search.js | 新增 ~660 行，独立模块，含 Insert/Shift/Swap 三邻域 |
auto-arrange.js | 新增阶段5禁忌搜索集成块（~30行），含开关读取和 try/catch |
constants/index.js | 新增 TABU_SEARCH 配置对象 |
settings.controller.js | DEFAULT_SETTINGS 新增 tabu_search_enabled |
SchedulingConfig.vue | 新增前端开关组件 |
tabu-search.test.js | 新增 11 个单元测试 |
三、预期效果评估
3.1 按数据场景分析
场景 A：数据宽松（教师容量充足，大部分班级能分配）
贪心已经能分配几乎所有班级，禁忌搜索的优化空间有限。预期提升：
| 指标 | 预期提升 | 用户感知 |
|---|---|---|
| 分配率 | +0-5% | 几乎无感 |
| 教材内聚度 | +5-10% | 略有改善 |
| 学院内聚度 | +5-10% | 略有改善 |
| 负载均衡 | +5-15% | 教师课时更均匀 |
| 综合评分 | +5-10% | 数据报表更好看 |
场景 B：数据紧张（教师容量吃紧，多课争抢教师，有较多未分配）
贪心的"先到先得"导致后处理课程质量差，禁忌搜索可通过链式调整显著改善。预期提升：
| 指标 | 预期提升 | 用户感知 |
|---|---|---|
| 分配率 | +15-30% | 未分配班级明显减少 |
| 教材内聚度 | +10-20% | 教师教的教材更集中 |
| 学院内聚度 | +10-20% | 教师教的学院更集中 |
| 负载均衡 | +15-25% | 教师工作量差异缩小 |
| 综合评分 | +15-30% | 排课质量明显提升 |
3.2 性能影响
| 维度 | 当前（贪心） | 加禁忌搜索后 |
|---|---|---|
| 单课程排课耗时 | 毫秒级 | 1-10 秒（取决于迭代次数） |
| 批量排课耗时 | 秒级 | 数十秒（仍在 5 分钟超时内） |
| 内存占用 | 低 | 略增（禁忌表，可忽略） |
| 前端等待体验 | 即时 | 可能需要 loading 提示 |
四、决策建议
4.1 何时值得升级
满足以下任一条件时，建议引入禁忌搜索：
- 批量排课后未分配班级数 > 总班级数的 5%
- 用户反馈排课结果"不合理"（教师跨多个学院、教材分散、工作量严重不均）
- 教师数量增长导致容量竞争加剧，贪心结果质量下降
- 需要支持更大规模的排课（100+ 教师、200+ 班级）
4.2 何时维持现状
满足以下全部条件时，当前算法够用：
- 批量排课分配率 > 95%
- 用户未反馈排课质量问题
- 数据规模稳定（教师 < 50，班级 < 100）
- 排课结果人工微调工作量可接受
4.3 下学期验证清单
下学期实际使用排课功能时，记录以下数据用于决策：
- [ ] 每次批量排课的总班级数、成功分配数、未分配数
- [ ] 未分配班级的诊断原因分布（容量满/无意向匹配/教材不匹配）
- [ ] 排课后人工调整的次数和调整幅度
- [ ] 教师 workload 分布（最高/最低/平均周课时）
- [ ] 教材内聚度统计（每位教师教的教材数分布）
- [ ] 学院内聚度统计（每位教师教的学院数分布）
- [ ] 用户对排课结果的主观满意度
4.4 对比测试方法
如果决定评估禁忌搜索的效果，可以用以下方式做对比：
- 导出当前学期的教师、班级、课程、排课数据
- 用当前算法跑一遍，记录各项指标
- 实现禁忌搜索后，用同样的数据跑一遍
- 对比两组指标
对比脚本可以放在 server/scripts/ 下，读取历史数据作为输入，两种算法各跑一次，输出对比报告。
五、实施路线（如决定升级）
5.1 工作量估算
| 阶段 | 工作内容 | 预估工时 |
|---|---|---|
| 问题建模 | 解表示、目标函数、邻域算子、硬约束 | 2-3 天 |
| 禁忌搜索主循环 | 禁忌表、接受准则、终止条件 | 1-2 天 |
| 集成 | 与现有五阶段贪心对接，保留 fallback | 1 天 |
| 测试验证 | 单元测试 + 历史数据对比 | 2-3 天 |
| 前端适配 | loading 状态、迭代进度展示（可选） | 0-1 天 |
| 合计 | 6-10 天 |
5.2 风险控制
- 五阶段贪心作为初始解完全保留，禁忌搜索是可选的优化层
- 通过双重开关控制：常量
TABU_SEARCH.ENABLED（静态）+system_settings表tabu_search_enabled（动态） - 关闭时行为与当前完全一致，零风险回退
- 超时保护：单课程 15 秒上限，超时则返回贪心初始解
- 异常保护：try/catch 包裹，异常时跳过优化并记录日志
5.3 更远期方案
如果未来数据规模增长到禁忌搜索也扛不住（教师 200+、班级 500+），可以考虑：
- Google OR-Tools CP-SAT：精确求解，中小规模秒级出最优解，但引入 Python 依赖，部署复杂度显著增加
- 遗传算法：适合多目标优化，但实现复杂、调参多
- 混合方案：禁忌搜索做粗优化 + CP-SAT 做精优化
当前阶段不建议引入 OR-Tools，优先用纯 JS 的禁忌搜索，保持部署简单。
禁忌搜索已于 v2.21.0（2026-07-06）实现并集成。默认关闭，待下学期实际排课数据验证效果后决定是否默认启用。