自动排课系统实战：贪心+局部搜索实现课程表算法-北京尧图网络

简介自动排课系统是一套面向学校教务人员与教育信息化学习者的课程表生成工具核心目标是在教师时间冲突、教室资源分配等约束下自动产出合理课表。系统支持设置节数、主课与副科优先级、上午与下午课程数量以及晚自习安排并借助遗传算法等优化策略对候选方案进行评估筛选适合用于理解排课算法原理或二次开发参考。压缩包共334个文件以272个class与52个java源码为主另含png示意图、pdf说明文档及工程配置文件整体约573KB便于直接运行或研读实现细节。目前已有3649人学习下载。通过源码与配套文档读者可梳理遗传算法在排课场景中的编码、适应度评估与分组流程理解主副科与时段约束的建模方式并参考示例封面与流程图快速上手为教育管理类应用的算法实践提供可复用的思路。1. 排课系统课程表从手工排到算法排的落地切口每学期开学前两周教务办公室里最常出现的画面是一台电脑开着 Excel几十个班级、上百门课、几十位老师的约束条件挤在一张表里改一个格子牵动一片红。手工排课的问题不在于慢而在于约束一多就不可控——老师时间冲突、教室容量不匹配、同一门课连排四节、体育课排在上午第一节这些规则靠人眼盯盯到第三遍就开始出玄学错误。这套自动排课系统课程表要解决的就是这件事把排课规则显式建模用算法生成一张满足硬约束、尽量优化软约束的课表并给出可人工微调、可导出、可查冲突的完整闭环。它适合两类人正在做毕设/课设、需要一套结构完整可交付方案的学生以及要给小型教务场景搭一套能跑起来的排课工具的开发同学。下面按需求、设计、实现、避坑、验收的顺序把整套方案拆开讲。2. 需求与约束建模先把排课规则翻译成机器能算的东西排课系统的成败八成在动手写代码之前就决定了。很多人一上来就想“用什么算法”结果约束没理清算法再花哨也排不出能用的表。我一般会先做一件事把教务老师嘴里的规则逐条翻译成硬约束违反即无效和软约束违反扣分但可接受。这一步做扎实后面的算法选型和数据结构才有依据。2.1 硬约束与软约束的分层硬约束是排课结果的底线任何一条被违反这张课表就不能交。典型的有四类教师时间冲突同一老师同一时段只能上一门课、班级时间冲突同一班级同一时段只能上一门课、教室冲突同一教室同一时段只能排一门课、教室容量与课程人数匹配容量不足直接无效。软约束则是“尽量满足”的偏好比如某老师偏好上午、某门课希望连排两节、体育类课程尽量不排第一节、同一班级的课尽量分散到一周不同天。把这两类分开的意义在于算法只需要保证硬约束绝对成立软约束用罚分函数去逼近这样即使最终解不完美也是一张合法可用的课表而不是一堆冲突。建模时我习惯用一张约束清单表把规则固化下来避免开发到一半又冒出“哦对实验室课要连排”这种返工约束类型具体规则归属处理方式教师冲突同一教师同一时段仅一门课硬排课时校验冲突即回退班级冲突同一班级同一时段仅一门课硬同上教室冲突同一教室同一时段仅一门课硬同上容量匹配教室容量 ≥ 课程选课人数硬候选教室预筛教师偏好某教师偏好某几个时段软罚分加权连排需求实验课连续两节软罚分加权分布均衡同班课程分散到不同天软罚分加权这张表不是给老师看的是给写代码的人看的。每加一条规则先问一句它属于硬还是软硬约束进校验函数软约束进目标函数边界清晰后面调参才不会乱。2.2 数据模型课程、教师、班级、教室、时段五张核心表排课系统的数据模型不需要花哨五张核心表就能撑起整个场景。课程表存课程名、课时数、选课人数、是否需要连排教师表存教师 ID 和偏好时段班级表存班级 ID 和人数教室表存教室 ID、容量、类型普通/实验室时段表把一周切成若干节每节有星期和节次两个维度。关键在于时段要离散化——把“周一第 1-2 节”当成一个可枚举的槽位而不是连续时间这样冲突检测就退化成集合判重实现简单且不容易出错。-- 核心表结构简化版字段按实际场景增删 CREATE TABLE course ( id INT PRIMARY KEY, name VARCHAR(64) NOT NULL, hours INT NOT NULL, -- 总课时决定占几个槽位 students INT NOT NULL, -- 选课人数用于教室容量匹配 need_block TINYINT DEFAULT 0 -- 1 表示需要连排 ); CREATE TABLE teacher ( id INT PRIMARY KEY, name VARCHAR(32) NOT NULL, prefer_slot VARCHAR(128) -- 偏好时段逗号分隔的槽位 ID ); CREATE TABLE classroom ( id INT PRIMARY KEY, capacity INT NOT NULL, type VARCHAR(16) DEFAULT normal -- normal / lab ); CREATE TABLE timeslot ( id INT PRIMARY KEY, weekday TINYINT NOT NULL, -- 1-5 period TINYINT NOT NULL -- 1-6每天 6 节 ); -- 排课结果表一条记录某课程占用某时段某教室 CREATE TABLE schedule ( id INT PRIMARY KEY, course_id INT NOT NULL, teacher_id INT NOT NULL, class_id INT NOT NULL, room_id INT NOT NULL, slot_id INT NOT NULL, UNIQUE KEY uk_room_slot (room_id, slot_id), UNIQUE KEY uk_teacher_slot (teacher_id, slot_id), UNIQUE KEY uk_class_slot (class_id, slot_id) );这里有个设计细节值得说schedule表上直接建了三个唯一索引把“教室不冲突、教师不冲突、班级不冲突”三条硬约束交给数据库兜底。应用层算法负责生成候选解数据库负责最后一道防线——即使算法有 bug 漏判插入时也会被唯一键拦下来。这种“算法数据库双保险”的做法是我在排课这类强约束场景里踩过坑之后养成的习惯比单纯信任内存校验稳得多。2.3 为什么选“贪心局部搜索”而不是纯遗传算法技术选型上排课是典型的 NP 难问题理论上可以用遗传算法、模拟退火、约束规划求解器。但落到实际项目里我一般不会一上来就上遗传算法原因很实在遗传算法的编码、交叉、变异设计复杂参数种群大小、变异率调起来玄学而且结果不可复现——同一个输入跑两次结果不同答辩时老师问“为什么这张表长这样”你很难解释。相比之下“贪心构造初始解局部搜索优化软约束”的组合更可控贪心保证快速得到一张合法表局部搜索交换两个槽位、尝试降低罚分负责把软约束慢慢磨好每一步都有明确的罚分变化可解释、可调试、可复现。具体做法是先按“约束最紧的课程优先”排序课时多、连排需求、教师偏好窄的排前面逐门课找第一个不冲突的槽位放进去得到初始解然后进入局部搜索循环随机挑两个已排课程尝试交换槽位如果交换后总罚分下降就接受否则回退循环固定轮数或罚分不再下降为止。这个思路在中小规模几十个班、上百门课下完全够用而且代码量可控适合作为毕设/课设的主体算法。3. 总体架构与模块划分四层结构撑起一套可交付系统需求理清之后架构要回答的是“这套系统由哪几块组成、每块负责什么、数据怎么流”。排课系统不需要微服务那套重架构单体分层足够关键是职责边界清楚让算法、数据、接口、界面各管一摊改一处不牵动全身。3.1 四层架构与数据流我一般把系统切成四层数据层表结构、DAO、算法层约束校验、初始解构造、局部搜索优化、服务层排课任务编排、结果持久化、冲突查询、接口/展示层REST 接口课表视图。数据流是单向的接口层接收“发起排课”请求 → 服务层加载课程/教师/教室/时段数据 → 算法层生成课表 → 服务层写库 → 接口层返回结果和罚分报告。这个单向流的好处是算法层是纯函数式的——输入数据、输出排课结果不碰数据库、不碰 HTTP单测好写出问题也好定位。# 算法层入口纯函数输入数据字典输出排课结果与罚分 def generate_schedule(courses, teachers, rooms, slots, max_iter5000): # 1. 贪心构造初始解 schedule greedy_construct(courses, teachers, rooms, slots) if schedule is None: return None, 无可行解请检查硬约束是否过紧 # 2. 局部搜索优化软约束 best schedule best_penalty total_penalty(best, teachers) for _ in range(max_iter): cand neighbor_swap(best, slots) # 随机交换两个槽位 if cand is None: continue p total_penalty(cand, teachers) if p best_penalty: # 只接受更优解简单但有效 best, best_penalty cand, p return best, best_penalty这段代码是整个系统的核心骨架。greedy_construct负责快速拿到合法解neighbor_swap生成邻域解total_penalty计算软约束罚分。参数max_iter控制搜索轮数太小优化不充分太大耗时上升实际项目里我一般按课程规模取 30008000跑一次几秒到十几秒完全在可接受范围。注意这里用的是“只接受更优解”的爬山策略没有引入模拟退火的概率接受原因是排课场景对结果稳定性要求高宁可少优化一点也不希望结果跳来跳去。3.2 约束校验模块硬约束的唯一裁判约束校验模块是硬约束的唯一裁判所有“这个槽位能不能放”的判断都走它避免校验逻辑散落在各处导致口径不一致。核心是一个is_valid函数输入课程、教师、教室、槽位和当前已排结果返回布尔值。实现上就是把三条冲突规则和容量规则各写一遍用集合或数据库唯一键的思路判重。def is_valid(course, teacher_id, room, slot_id, placed): # placed: 已排结果列表元素含 teacher_id/class_id/room_id/slot_id for item in placed: if item[slot_id] ! slot_id: continue if item[teacher_id] teacher_id: # 教师冲突 return False if item[class_id] course[class_id]: # 班级冲突 return False if item[room_id] room[id]: # 教室冲突 return False if room[capacity] course[students]: # 容量不足 return False return True这个函数看着朴素但它是整个系统正确性的地基。实际项目里我会给它配一组单元测试把“教师冲突、班级冲突、教室冲突、容量不足”四种情况各造一个用例确保每次改动后校验逻辑不退化。很多排课系统的 bug 不是算法不行而是校验漏了一种情况结果导出的课表里藏着冲突教务老师一用就翻车。3.3 排课任务编排与结果持久化服务层负责把“发起排课”这件事编排成一次完整任务加载数据 → 调算法 → 写结果 → 生成罚分报告。这里有两个工程细节值得注意。第一排课要能重跑教务场景里规则经常微调重跑一次要能覆盖旧结果所以写库前先按学期清空旧schedule记录再批量插入新结果整个过程放在一个事务里避免中途失败留下半张表。第二罚分报告要落库或落文件光给一张课表老师不知道哪里做了妥协把每条软约束的违反次数统计出来答辩和验收时都是加分项。def run_scheduling_task(term_id): data load_term_data(term_id) # 加载课程/教师/教室/时段 result, penalty generate_schedule(**data) if result is None: return {ok: False, msg: penalty} with db.transaction(): db.execute(DELETE FROM schedule WHERE term_id %s, term_id) db.batch_insert(schedule, result) report build_penalty_report(result, data[teachers]) return {ok: True, penalty: penalty, report: report}load_term_data把五张表的数据组装成算法层要的字典build_penalty_report按软约束类型统计违反次数。事务包裹删除和插入保证“要么全换新要么保持旧表”这是排课这种批量覆盖场景的基本要求少了这一步中途异常就会让课表处于半新半旧的尴尬状态。4. 核心算法实现贪心构造与局部搜索的工程细节架构搭好之后真正决定课表质量的是算法实现。这一章把贪心构造、邻域交换、罚分函数三块拆开讲每块都给可运行的代码和参数说明读者可以照着改。4.1 贪心构造按约束紧度排序的插入策略贪心构造的核心思想是“难排的先排”。约束越紧的课程可选槽位越少越应该优先占位如果先排了宽松的课把好槽位占了紧约束的课就可能无解。排序键我一般用三个维度加权课时数多者优先、是否连排连排优先、教师偏好槽位数少者优先。排的时候对每门课遍历所有候选槽位用is_valid校验第一个通过的即插入。def greedy_construct(courses, teachers, rooms, slots): # 按约束紧度排序课时多、需连排、偏好窄的优先 def tightness(c): pref len(teachers[c[teacher_id]][prefer_slot].split(,)) return (-c[hours], -c[need_block], pref) ordered sorted(courses, keytightness) placed [] for c in ordered: candidates [s for s in slots if room_fits(c, rooms)] ok False for s in candidates: room pick_room(c, rooms, placed, s[id]) if room and is_valid(c, c[teacher_id], room, s[id], placed): placed.append({ course_id: c[id], teacher_id: c[teacher_id], class_id: c[class_id], room_id: room[id], slot_id: s[id] }) ok True break if not ok: return None # 某门课无槽位可放整体失败 return placedtightness返回的元组用负数实现降序pick_room在满足容量的教室里挑一个当前槽位空闲的。这里有个容易忽略的点连排课程要占连续两个槽位上面的简化代码只处理了单槽位实际实现里need_block1的课程要一次校验两个相邻槽位都合法才插入否则连排需求形同虚设。贪心失败返回None时不要直接报错给用户而是提示“硬约束过紧建议放宽某条规则”把问题定位信息带出去这是排课系统好不好用的分水岭。4.2 邻域交换与罚分函数软约束怎么量化局部搜索的效果取决于两件事邻域怎么定义、罚分怎么算。邻域我选“随机挑两个已排课程交换槽位”简单且覆盖面够罚分函数则把每条软约束翻译成一个可累加的数值。教师偏好违反一次罚 10 分连排需求未满足罚 20 分同班课程集中在同一天罚 5 分/次具体权重按业务重要性调没有标准答案但权重要写进配置文件方便验收时演示“调大某权重后课表如何变化”。def total_penalty(schedule, teachers): score 0 for item in schedule: t teachers[item[teacher_id]] if str(item[slot_id]) not in t[prefer_slot].split(,): score 10 # 教师偏好违反 # 连排检查同课程相邻槽位是否成对 if not has_block_pair(item, schedule): score 20 # 连排未满足 score day_concentration_penalty(schedule) # 同班课程集中度 return scorehas_block_pair检查某课程是否真的占了相邻两个槽位day_concentration_penalty统计每个班每天课程数超过阈值就累加罚分。这套罚分函数的好处是每一项都可解释验收时老师问“为什么这门课排在下午”你能指着报告说“因为上午槽位被更紧约束的课占了交换过来罚分反而上升”。可解释性在答辩场景里比多优化几分重要得多。4.3 冲突检测与结果导出排完课不等于交付完成还要能查冲突、能导出。冲突检测分两层算法层在插入时已经保证硬约束但为了防御性编程导出前再跑一遍全量校验把任何残留冲突列出来导出则支持 CSV 和 Excel 两种格式列包括星期、节次、班级、课程、教师、教室按班级或按教师两个视角各导一份教务老师拿去直接打印张贴。def export_timetable(schedule, viewclass): rows [] for item in schedule: rows.append({ 星期: weekday_name(item[slot_id]), 节次: period_of(item[slot_id]), 班级: item[class_id], 课程: item[course_id], 教师: item[teacher_id], 教室: item[room_id] }) rows.sort(keylambda r: (r[星期], r[节次], r[view_key(view)])) return rows导出前先validate_all(schedule)跑一遍全量硬约束校验有冲突就拒绝导出并返回冲突清单逼着使用者先修数据再出表。这个“导出前强制校验”的习惯是我被“导出的表里有冲突、打印后才发现”坑过一次之后加上的成本很低收益很高。5. 避坑与常见问题排课系统最容易翻车的五个点排课系统的坑大多不在算法本身而在数据、边界和工程细节上。下面五条是我在类似项目里真实遇到或见别人踩过的按“现象 → 原因 → 解决”写清楚读者可以对照自查。5.1 排课跑不出结果报“无可行解”现象点“开始排课”后算法返回空提示无可行解但数据看起来没毛病。原因通常是硬约束之间本身矛盾比如某班级总课时数超过了可用槽位数或者某教师的偏好时段被当成硬约束写死导致可选槽位为零。解决先做一次可行性预检统计每个班级的课时需求与可用槽位比、每个教师的可选槽位是否为空把矛盾在排课前就暴露出来而不是让算法跑到一半失败。预检通过再进算法失败信息要具体到“哪个班课时超了、哪个教师无槽位”。5.2 课表能排出来但同一门课连排四节现象算法跑通了硬约束也满足但导出后老师发现某门课一上午连上四节学生崩溃。原因连排需求只做了“至少两节连续”的软约束没有做“单日上限”的硬约束或强罚分。解决在罚分函数里加一条“同课程单日超过 N 节重罚”或者在硬约束里直接限制单日上限。我一般把单日上限设成 2 节连排课或 1 节普通课作为硬约束处理因为这条一旦违反课表基本不可用不值得用软约束去赌。5.3 重跑排课把旧课表覆盖了一半现象规则微调后重跑中途数据库连接断了结果旧课表被删、新课表没写全课表处于半残状态。原因删除和插入没有放在同一事务里或者批量插入分批提交。解决整个“清空写入”包在一个事务里批量插入用单条多值 INSERT 或事务内批量提交任何一步失败整体回滚。这条是纯工程问题但排课系统里特别容易忽略因为大家注意力都在算法上。5.4 教室容量匹配了但类型不匹配现象硬约束全过课表合法但实验课被排进了普通教室老师到了教室发现没设备。原因容量匹配只校验了人数没校验教室类型与课程类型的对应关系。解决在is_valid里加一条类型校验课程带need_lab标记时只允许typelab的教室。这类“隐性硬约束”最容易被漏建议在需求阶段就把课程类型和教室类型的对应表列出来逐条落到校验函数里。5.5 罚分权重调来调去结果忽好忽坏现象调大教师偏好权重后连排需求大面积不满足调大连排权重后教师偏好又崩了。原因软约束之间互相竞争权重没有分层单点调参必然此消彼长。解决给软约束分优先级高优先级权重设成数量级差距比如连排 100、偏好 10、分布 1让算法优先保高优先级同时把权重外置到配置文件验收时演示“改权重 → 课表变化”的对应关系而不是在代码里硬编码。调参这件事没有银弹分层加权可复现的对比报告比反复试数字靠谱。6. 验收与答辩怎么证明这套排课系统真的能用验收排课系统不能只看“跑通了、有课表”要拿证据说话。我一般准备三样东西一张约束覆盖表、一份罚分对比报告、一组边界用例。约束覆盖表把第 2 章列的每条硬/软约束逐条对应到代码位置和测试用例答辩时老师问“教师冲突怎么保证的”直接指到is_valid和对应的单测罚分对比报告展示“贪心初始解 vs 局部搜索后”的罚分下降曲线证明优化确实起了作用边界用例包括“课时刚好占满槽位”“某教师只有一个可选槽位”“连排课只剩一组连续槽位”这类极端情况跑通说明系统不是只在顺境下能用。具体验收步骤可以按这个顺序走先导入一份构造好的测试数据3 个班、10 门课、5 位教师、4 间教室跑一次排课检查硬约束零违反再手动改一条规则比如把某教师偏好从上午改成下午重跑对比罚分报告里对应项的变化最后导出 CSV用脚本或人工抽查 10 条记录核对星期、节次、教室是否与库内一致。这套流程走下来系统能不能交付基本就有数了。验收项通过标准检查方式硬约束零违反教师/班级/教室冲突数 0全量校验脚本容量与类型匹配无超容量、无类型错配抽查校验函数软约束可优化局部搜索后罚分低于初始解罚分对比报告结果可复现同输入同参数结果一致连跑两次比对导出正确导出内容与库内一致抽查 10 条答辩时最容易被问倒的不是算法多复杂而是“你这个结果为什么是这样”。所以我在演示时习惯先讲约束分层再讲贪心为什么这么排序最后打开罚分报告指着一项说“这里违反了 3 次教师偏好是因为连排优先级更高我们做了取舍”。把取舍讲清楚比声称“我的算法最优”可信得多。从那以后我每次做排课类项目都会在写第一行算法代码之前先把约束清单和验收表列出来跑完再回头逐条对——这套习惯让我少返工了很多次。希望帮到你。本文还有配套的精品资源点击获取

自动排课系统实战：贪心+局部搜索实现课程表算法

相关推荐

t3code：个人开发工作台的模板、片段与脚本实战

SLAM系统中紧耦合与松耦合设计模式解析与实践

SLAM系统中耦合度设计：紧耦合与松耦合实践解析

更多资讯

车企智能诊断做不深？车云数据架构才是关键瓶颈

微软Copilot三合一与按量计费：智能体成本控制与开发选型指南

从模型核查到智能汽车竞赛：AI系统可靠性与多Agent协作实践

消防科普教育展馆设计与技术创新应用

5G LDPC MATLAB实现：基图选择、速率匹配与避坑指南

Informer长序列预测：ProbSparse注意力与生成式解码器实战

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？