简介自动排课系统是一套面向学校教务场景的课程表自动生成方案基于遗传算法等智能优化方法处理教师冲突、教室资源、主课副科优先级及上午/下午节数、晚自习等多重约束帮助教务人员快速获得合理课表也适合算法学习与二次开发。压缩包共334个文件约573KB其中Java源文件有50余个编译后的class文件占多数另含PNG算法流程图、PDF说明文档及工程配置整体结构清晰便于对照代码梳理实现思路。源码中的遗传算法核心类展示了种群初始化、分组、适应度评估与迭代进化基础数据类则负责课程、年级和分组信息管理读者可从运行示例出发追踪排课结果生成全过程理解算法参数与业务条件的映射关系。已有3646人学习下载适合教育信息化从业者、教务管理员及希望掌握排课算法实现的Java开发者参考。1. 自动排课系统不是在填课表它是在一张多约束网里找可行解自动排课系统课程表最容易踩的第一个坑是把它当成“把课程列表填进周一至周五的格子”。实际的排课问题是一张由班级时间、教师时间、教室容量三类约束交织成的网班级在同一时间只能上一门课教师在同一时间只能出现在一个教室教室容量不能超、课程连排不能断这些条件同时成立才叫一个可行解。我最早做教务系统时用过纯贪心老师上午刚上完三节连排下午又被排课数据一多直接翻车。这个方向真能落地的话能替高校教务处、培训机构和 K12 学校省下大量人工核对时间。下面从建模、求解器选型、最小实现到排错按我实际做过的方式讲一遍。2. 把排课问题翻译成约束模型三类硬约束与两类软约束的取舍写排课代码前先做建模。把真实排课需求翻译成约束条件时这些条件分成两个角色硬约束负责过滤出合法区域软约束决定哪块合法区域更让人满意。很多第一次做排课系统的人把这两类混在一起结果就是解不出来或者解出来不敢用。2.1 硬约束先立住时间、教师、班级与教室四个维度硬约束是“违反任何一条课表就没法执行”的条件。我一般用assign[course] time_slot这个视角来建模每个课程是一个变量变量的取值是某个时间段然后在这个基础上加约束。第一类约束是班级内部不冲突。同一个班级的所有课程必须分配到互不相同的时间段否则一个班在同一时间会上两门课。第二类约束是教师不冲突。同一个教师名下的课程同样要两两不同时间因为一位老师没法同时出现在两间教室。第三类约束是教室不冲突。如果是走班制同一个时间段里所有课程使用的教室必须互不相同而且选教室时要满足容量大于选课人数。一个常见的简化做法是“固定教室制”每个班级绑死一间教室那么教室约束退化成“班级不冲突”此时可以不单独建模教室维度。K12 学校大多是这种情况高校走班制才需要把教室真正加进模型。把容量校验放在数据预处理阶段读入课程时如果某门课人数超过可用教室容量直接报错不要等求解器跑完才暴露。2.2 软约束决定体验均匀分布、晚课最少与连排硬约束解决“能不能用”软约束解决“好不好用”。同一个合法课表里可能有一版所有课都堆在上午另一版均匀分布两者都不违反硬约束但师生感受完全不同。软约束通常有这几类教师单日课时上限比如一天最多 4 节、晚课尽量少、课程在周内均匀分布、连排请求尽量满足。这些不能放进硬约束否则会直接把解空间压没正确做法是把它们写成目标函数里的惩罚项求解器在满足硬约束的前提下尽量降低惩罚值。权重的经验值是拉开量级。晚课少排一节的惩罚设为 5教师单日超过 4 节的惩罚设为 20连排未满足的惩罚设为 10。权重太接近求解器会拿“多几节晚课”去换“教师单日少超一节”排出来的课表看起来数字没差用起来处处别扭。这个调权重的过程有点像玄学但核心原则是先保教师体力再保学生体验最后保形式上的均匀。2.3 输入建模课程、教师、教室三张 CSV 表的字段设计我不建议直接在代码里写死课程数据生产环境第一版就上 CSV 或数据库表后面接教务系统导入会轻松很多。最少需要三张表课程表、教师表、教室表。文件字段说明courses.csvcourse_id, class_name, subject, teacher_id, weekly_hours, require_consecutive, prefer_no_latecourse_id 是主键teacher_id 指向教师表weekly_hours 决定这个课程每周上几节require_consecutive 为 1 时表示需要连排teachers.csvteacher_id, teacher_name, unavailable_slotsunavailable_slots 记录禁排时段用2-3;4-2编码表示第 2 天第 3 节、第 4 天第 2 节rooms.csvroom_id, room_name, capacitycapacity 在固定教室制下不参与约束但保留字段用于走班制扩展读取时有一个容易忽略的细节用utf-8-sig编码打开 CSVExcel 导出的文件会带 BOM 头直接按utf-8读会把第一个字段名读成\ufeffcourse_id。另外每行做一遍 strip防止教师 ID 或班级名里混进前导/尾部空格。import csv def load_courses(path): courses [] with open(path, encodingutf-8-sig) as f: for row in csv.DictReader(f): row {k.strip(): v.strip() for k, v in row.items()} courses.append(row) return courses这段代码没有排课逻辑但它决定了后面所有数据质量的起点。strip 掉空格后要做一次引用完整性检查所有课程里的 teacher_id 必须存在于教师表否则直接报错。排课系统里最耗时的不是求解而是排查脏数据。3. 选对求解器从回溯到 CP-SAT 的演进路径与选型判断模型搭好后下一步是选一个求解器。市面上能搜到遗传算法排课、模拟退火排课、回溯排课还有直接用 Python 手写贪心排课的各说各话。我的判断标准很简单解空间大小和约束复杂程度决定工具而不是哪个框架听起来更时髦。3.1 贪心为什么会在第 80 门课时卡死贪心算法的思路是“按优先级遍历课程每门课塞到第一个空闲时间段”。它跑得快小规模数据用起来非常顺手但排到后面会遇到一个尴尬场景某位教师只在周五有时间而周五的空闲时段已经被前面排课占满此时只能回退重排。回退正是贪心算法的短板。排课问题的约束是全局的前面的局部最优选择会压缩后面的解空间这不是靠“再多试几次随机顺序”能稳定解决的问题。数据量小比如一个年级 20 门课贪心加随机扰动完全够用一旦到全校几百门课贪心排出的课表经常出现“最后十几门课无家可归”的情况。这不是代码写得不好是算法本身的局部性决定的。如果你评估后确认自己的场景只有“不冲突”这一个约束可以直接用贪心但凡有连排、合班、教师禁排任何一项直接往下看。3.2 CP-SAT 的全局约束AllDifferent、ExactlyOne 与 AllowedAssignments我目前最常用的求解器是 OR-Tools 里的 CP-SAT。它是约束编程求解器核心思想不是“试探—回退”而是“约束传播”给变量赋值后约束会把其他变量的可行域进一步缩小缩小到极限才分支搜索。这个过程把大量不可行分支提前砍掉搜索效率比裸回溯高一个量级。CP-SAT 提供的三个全局约束基本覆盖了排课场景。AllDifferent 强制一组变量两两不同用在上文说的班级内部不冲突、教师不冲突。ExactlyOne 表示一组布尔变量里恰好有一个为 True适合表达“某课程必须落在可选时间段集合中的某一个”。AllowedAssignments 直接给一组变量指定合法的取值组合适合处理教师禁排、特定班级不能在特定时间上课这类映射关系。还有一个迭代优势CP-SAT 的模型是声明式的改需求时不改求解逻辑只改约束条件或目标函数。学校教务这种“每周都有新要求”的场景这一点比手写回溯值得多。3.3 规模边界对照100 个时段以内与 1000 个时段以上怎么选场景时间槽规模推荐方案单个年级、只有不冲突约束小于 100贪心 随机扰动或直接手写回溯代码量小且好维护全校排课、有教师禁排/连排/合班100 到 1000CP-SAT把硬约束加全目标函数里放软约束大学整学期、走班制、多校区教室大于 1000CP-SAT 分阶段求解先固定每周框架再细化到每天配合初始解提示这里有一个重要边界不是数据量越大越要上复杂算法而是约束的交互程度决定算法。1000 个课程变量全部只是“时间不冲突”用 CP-SAT 也能跑但贪心加冲突检测后处理也许一天就写完。反过来200 门课但存在大量合班课和教师跨校区移动贪心已经无法维护这些关系此时直接用 CP-SAT 是更稳妥的选择。遗传算法和模拟退火我也试过它们适合“目标函数精确但硬约束复杂”的优化问题排课里硬约束恰恰是不能讨价还价的调惩罚函数调得心累最后我放弃了这条路线。4. 用 OR-Tools 实现最小可用自动排课Python 骨架与三个必调参数这一章给一个能直接跑的最小模型。它简化了教室维度假设固定教室制保留了班级不冲突、教师不冲突两类硬约束以及两项目标函数。跑通这个骨架后再往自己的数据上扩展。4.1 变量定义与硬约束一个可直接运行的 CP-SAT 模型假设有 3 个班级每班 5 门课每周上 1 次共 15 门课排课周期是 5 天每天 4 节共 20 个时间槽。5 位教师各教 3 门课。from ortools.sat.python import cp_model # 时间槽5天 x 4节 20 days range(5) periods range(4) n_slots len(days) * len(periods) # 课程与教师的对应关系 classes [ClassA, ClassB, ClassC] subjects [Math, English, Physics, History, PE] teacher_of { (ClassA, Math): T1, (ClassB, Math): T1, (ClassC, Math): T1, (ClassA, English): T2, (ClassB, English): T2, (ClassC, English): T2, (ClassA, Physics): T3, (ClassB, Physics): T3, (ClassC, Physics): T3, (ClassA, History): T4, (ClassB, History): T4, (ClassC, History): T4, (ClassA, PE): T5, (ClassB, PE): T5, (ClassC, PE): T5, } model cp_model.CpModel() # 变量每门课排到哪个时间槽取值 0..19 course_vars {} for cls in classes: for sub in subjects: name f{cls}_{sub} course_vars[(cls, sub)] model.NewIntVar(0, n_slots - 1, name) # 硬约束1同一个班级的课程时间两两不同 for cls in classes: model.AddAllDifferent([course_vars[(cls, sub)] for sub in subjects]) # 硬约束2同一位教师的课程时间两两不同 by_teacher {} for (cls, sub), teacher in teacher_of.items(): by_teacher.setdefault(teacher, []).append(course_vars[(cls, sub)]) for teacher, vars_ in by_teacher.items(): model.AddAllDifferent(vars_) # 软约束晚课每天第3、4节尽量少 bad_slots [d * len(periods) p for d in days for p in (2, 3)] penalties [] for var in course_vars.values(): for bs in bad_slots: penalties.append(var bs) model.Minimize(sum(penalties)) solver cp_model.CpSolver() solver.parameters.max_time_in_seconds 10.0 solver.parameters.num_search_workers 8 solver.parameters.log_search_progress True status solver.Solve(model) print(status:, solver.StatusName(status)) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): for (cls, sub), var in course_vars.items(): idx solver.Value(var) day, period divmod(idx, len(periods)) print(f{cls} {sub}: 周{day 1} 第{period 1}节)这段代码的关键点在于两个 AddAllDifferent。第一次看排课模型的人总觉得要写“遍历每个时间段判断有没有冲突”但 CP-SAT 的全局约束把这一步变成了声明式的你告诉求解器“这些变量必须两两不同”剩下的传播和剪枝由求解器内部完成。var bs这种写法在 CP-SAT 里返回一个 0/1 线性表达式可以直接被 sum 累加进目标函数不用手动建布尔变量。硬约束只用了两个 AllDifferent是因为固定教室制下班级和教师不冲突就已经保证同一时间不会有人挤在同一间教室。如果做走班制需要把变量扩展成时间和教室的组合参考 5.4 里的说明。4.2 把软约束放进目标函数惩罚项的最小写法上述代码里已经有一个最简单的软约束晚课惩罚。实际生产里还有一个高频需求是控制教师单日课时上限这里给出可复用的模板。# 软约束每位教师每天最多上2节超出部分计入惩罚 for teacher, vars_ in by_teacher.items(): for d in days: daily_count sum(v // len(periods) d for v in vars_) over model.NewIntVar(0, len(periods), fover_{teacher}_{d}) model.Add(daily_count 2 over) penalties.append(over * 20)v // len(periods)把时间槽索引还原成“星期几”然后和当前天 d 比较得到该教师在这一天的上课节数。over是超出 2 节的数额乘 20 作为惩罚值。注意这里不能在原有penalties列表上重复追加否则会叠加多个 Minimize 表达式。正确的做法是在建模开始时初始化一个penalties []把所有软约束的惩罚项都 append 进去最后只调一次model.Minimize(sum(penalties))。这个模板的扩展性很好。想加“课程均匀分布”就统计每班每天的上课节数对偏离平均值的部分加惩罚想加“连排请求”就把连排建模成两个变量取相邻索引的强约束未满足时加惩罚。所有软约束都往这个列表里塞目标函数不用改。4.3 三个必调参数num_search_workers、max_time_in_seconds 与 log_search_progressCP-SAT 默认参数能跑通小模型但生产环境一定要主动设置以下三个参数。num_search_workers 是并行工作线程数。默认 0 表示自动选择。我的习惯是变量少于 500 时不设这个参数多线程的通信开销反而拖慢求解变量超过 500 后设为 CPU 核数减一。曾有一次我为了图快把 16 核机器全开结果求解时间比 8 线程还长后来不再迷信“核越多越好”。max_time_in_seconds 是求解时间上限。生产环境必须设置否则遇到难解实例可能跑几小时没有结果。我一般先给 30 秒跑通确认模型正确后再按需求放宽到 120 秒。CP-SAT 在超时后会返回当前找到的最好的可行解状态是 FEASIBLE 而非 OPTIMAL使用方需要接受这一点。log_search_progress 是求解过程日志开关。第一次跑通模型时打开能直观看到约束传播在砍变量域、搜索分支在收敛生产环境关掉因为日志量大到能撑满磁盘。判断模型是不是“无解但看起来应该有解”时这个日志是最直接的证据来源。solver.parameters.max_time_in_seconds 30 solver.parameters.num_search_workers 8 solver.parameters.log_search_progress True提示CP-SAT 不是命令式编程它不会按你写代码的顺序“执行”约束。改约束后一定要重新求解不要在内存里复用旧模型实例。5. 自动排课避坑5 个让我翻车过的问题与排查方法排课系统跑通容易跑稳很难。下面 5 个坑都是真实踩过的按“现象、原因、解决”写清楚希望你能绕过我的血泪经验。5.1 求解器返回 INFEASIBLE却不告诉你哪里冲突现象模型结构看起来没问题数据也就 15 门课、20 个时间槽但 solver.Solve 返回 INFEASIBLE日志里也没有明显错误。原因最常见的是时间槽数量不够或者某个教师被分配了超出其可用时间的课程量。另一个隐蔽原因是把“教师不可用时间”写成了硬约束而这个教师的总可用时间段少于他的上课节数导致约束传播直接判死。解决第一步把所有硬约束注释掉只剩变量确认模型能返回可行解第二步逐个放开硬约束每放开一个求解一次找到第一个让模型变成 INFEASIBLE 的约束问题就定位了。第二步检查教师维度每位教师的课程数是否小于等于他的可用时间槽数。这一步也可以用预处理代码做静态判断不要等求解器反馈。5.2 教师名字里的全角空格和重复 ID现象排出来的课表里出现了同一位教师在同一个时间上两门课第一反应是约束没加检查代码又发现 AddAllDifferent 明明写上了。原因CSV 里教师 ID 混进了全角空格或者行尾不可见字符例如T1与T1 被读成两个不同的教师。by_teacher 字典因此把原本是同一个人的课程拆成了两个教师组AllDifferent 自然管不到跨组的冲突。解决读取 CSV 后统一做 strip并对教师 ID 做唯一性校验如果去重后的数量少于原始数量直接打印警告提示可能存在隐藏字符。这个校验放在任何排课逻辑之前几分钟能排查完的问题不值得花一晚上调试。5.3 时间槽够用但求解器长时间找不到更优解现象模型有可行解但目标函数值长时间不下降CPU 时间飙到几百秒解的质量停在原地。原因排课模型有一个隐性问题——等价解太多。3 个班级的课表整体上下翻转或者一周内的排课镜像互换从约束角度看都是同一个解但求解器会把这些重复分支全部搜索一遍。解决加入对称性破坏约束。最简单的一招是固定某个班级第一门课的时间比如强制 ClassA 的 Math 排在时间槽 0其他解空间的对称分支就会被剪掉。也可以在班级维度上加顺序约束例如让 ClassA 的 5 门课按 subjects 列表的顺序递增这样同一个班级的课程排列方式就只剩一种。5.4 教室容量超限求解器完全不理会现象走班制场景下排课结果里出现 40 人的课程被分配到 30 人教室而模型状态显示 OPTIMAL。原因课程变量只建模了“时间”一个维度教室根本没有进入模型。这种情况下求解器确实不违反任何约束因为模型里压根没有容量约束它给出的最优解是在一个有缺陷的模型上的最优解。解决走班制必须把变量扩展成0 .. n_slots * n_rooms - 1的整数用除法和取模还原出时间和教室两个维度然后加“同一时间同一教室最多一门课”的约束。这个扩展会让解空间变大但同时也给软约束提供了新的优化维度——比如让课程尽量集中在某几栋教学楼避免学生课间长距离移动。5.5 软约束权重没拉开课表看似最优却没人想用现象目标函数值已经很低课表也满足所有硬约束但教务老师一看就摇头某个教师一天连排 6 节的情况出现了。原因晚课惩罚权重是 5教师单日超时惩罚也是 5求解器会认为“一天多上 2 节课”和“少 2 节晚课”没有区别迭代后自然挑了一条对教师更累的路径。解决把教师超时惩罚提到 20 以上晚课保持 5让惩罚值之间拉开量级。更稳妥的做法是提前做“权重冒烟测试”只保留一个软约束跑一轮看解是否符合直觉再叠加下一个软约束。权重调整不是一次性工作学校换了作息时间表之后原本合理的权重可能又要重新调。6. 从能跑到能上线课表冲突校验与 HTML 导出模型能输出课表只是第一步真正上线还要解决两个问题怎么确认结果可靠怎么让非技术同事能用上。6.1 排完课先别信独立校验脚本三分钟跑完求解器返回 OPTIMAL 不代表数据没问题它只代表“模型里的所有约束都满足了”。如果建模时漏了某个约束校验环节也发现不了。所以我保留了一个习惯用一套完全独立的、不用 OR-Tools 的脚本做最终校验把求解结果按“教师、班级”两个维度重新查一遍冲突。def validate(timetable, teacher_of): errors [] by_teacher {} for (cls, sub), (day, period) in timetable.items(): teacher teacher_of[(cls, sub)] by_teacher.setdefault(teacher, []).append((day, period, cls, sub)) for teacher, items in by_teacher.items(): points [(d, p) for d, p, _, _ in items] if len(set(points)) len(points): errors.append(fteacher {teacher} conflict) return errors这段校验代码只依赖纯 Python 的 set 去重逻辑逻辑简单到不可能出错。虽然与模型里的 AddAllDifferent 本质上是同一个检查但独立实现的好处是即使以后把求解器从 CP-SAT 换成别的工具这层校验依然有效。每次重新生成课表后先跑一遍校验再发出去。6.2 让教务老师能直接用HTML 课表导出课表最终要给教务老师和班主任看不能丢一份 JSON 或打印一堆控制台文本。我通常导出一个单文件 HTML行是节次、列是星期几直接在浏览器打开就能看和打印。def export_html(timetable, path): days [周一, 周二, 周三, 周四, 周五] lines [table border1 cellspacing0 cellpadding6] lines.append(trth节次/th .join(fth{d}/th for d in days) /tr) for period in range(4): lines.append(ftrtd第{period 1}节/td) for day in range(5): cells [f{cls}-{sub} for (cls, sub), (d, p) in timetable.items() if (d, p) (day, period)] lines.append(ftd{br.join(cells) if cells else }/td) lines.append(/tr) lines.append(/table) with open(path, w, encodingutf-8) as f: f.write(\n.join(lines))这段代码不复杂但它把技术结果翻译成了教务老师能直接用的东西。后续可以按班级分别导出文件名拿班级命名再配一个按教师维度的导出一线老师拿到手就能排监考和调课。6.3 我保留的一个习惯我现在拿到任何一个排课需求先问三件事满课率是多少、教室是固定还是走班、教师有没有禁排时间段。这三个答案基本决定了解空间大小和方案选型。课表问题做到后面难点已经不是算法本身而是把真实世界的约束翻译成模型、把脏数据挡在门外、把结果翻译回人话。希望帮到你。本文还有配套的精品资源点击获取