想写一个排课功能，请教大佬们

[yy306525121]

因为媳妇高中需要排课，享用程序给她写一个， 之前试了 timefold ，写出来之后由于规模太大， 两三个老师还能拍出来，数量一多之后连着跑了一两天也没跑出来，想问一下，除了 timefold 这种问题求解器之外， 还有什么简单的方法做这种排课程序，遗传算法是不是最简单的方式？

[通过 ortools 实现的 python 版代码已经在评论区贴出]

代码地址： https://raw.githubusercontent.com/yy306525121/school_scheduling/main/plan3.py

[lxdlam]

一个 off-topic：

Bill Gates 开始他的生涯基本就始于他高中时代跟 Paul 开始的开发合约，其中一个非常知名的就是给他的母校 Lakeside 开发了一个排课系统。根据 Paul 晚年书里所述，他甚至魔改了算法，帮他安排了一节除了他全是女生的英语课。

Ref:
- https://tatler.lakesideschool.org/3085/news/return-to-the-source-lakesides-scheduling-algorithm-explained/
- https://www.businessinsider.com/10-things-you-didnt-know-about-bill-gates-2011-4?op=1&IR=T#he-wrote-his-high-schools-scheduling-program-to-book-him-into-an-english-class-with-all-girls-3

[Pteromyini]

据我所知排课问题是典型的 NP-Hard 问题，不过要是单纯的想得到一个解而不是最优解还是不难，贪心或者局部贪心应该能得到一个解，遗传算法也能得到解

[yqf0215]

@yy306525121 08 年之后就不在教务处了，到其他部门了

[sindri]

做过教务，排过课，都是人工来干的。

找过网上收费的，也不贵，几百上千都有。试用一下，速度有点慢，限制真的多。一看就不像是专业人员设计的。

也想过自己做，用 python ，后来实力不允许，加上辞工，不了了之

是个痛，关注一下 UP 主的进度。

[dingyaguang117]

搜索 + 剪枝 可能效率高很多

[dingyaguang117]

原来这么大市场，突然间很感兴趣

[klo424]

看了一下，楼上基本都是云玩家。没真正做过排课的，不会知道他有多复杂。

op 可以参考我之前的一个贴子，https://www.v2ex.com/t/877476 。

虽然我做出来一个简单的排课系统，但是实际用起来还是需要一些人工处理，也是自己学艺不精，对算法研究不够，照市面上成熟的排课系统差远了。

提供个思路吧，可以搜索一下相关专利和论文，排课对算法的理解还是很高的，所以还是得从算法入手才能更好地实现。

[yy306525121]

@klo424 嗯， 我的算法也不是特别好， 之前都是直接用问题求解器建模扔给求解器的， 但是就是 NP 问题，求解问题的规模太大了。

[yy306525121]

@lxdlam 哈哈， 老哥牛逼

[yy306525121]

@dingyaguang117 好的， 相关算法我得再去学一下

[yy306525121]

@sindri 嗯，开个 VIP 是直接省事， 但是每个学校都有自己的个性化需要处理， 网上的不太好找全部满足的， 我这个排课也不是必须要做出来， 现在很多工作都是我媳妇自己做的， 我现在是空闲时间比较多， 加上这个工作学校每个月多给我媳妇补贴了一千五，我想着能利用我的空闲时间帮我媳妇省点功夫也挺好的。哈哈

[yy306525121]

@Pteromyini 可能是我对问题求解器用的还不够熟练，我也是写这个排课的时候现学的问题求解器，但是写出来的硬性约束太多了，能省的都省了，还是很慢，唉

[yy306525121]

@iosx 好的， 感谢大佬

[yy306525121]

@Firw 很有可能，我也是写这个排课的时候现学的问题求解器

[yy306525121]

@volvo007 好的，我好好研究这个遗传算法， 看看能不能用这个算法解决。

[yy306525121]

这个是之前使用 timefold （类似 optaplanner 的东西）排课的建模，并且遇到的问题的描述，感兴趣并且有时间的大佬可以抽空帮忙看看，是我哪里写的有问题吗

https://stackoverflow.com/questions/78886785/school-timetable-cant-get-result-within-a-certain-period-of-time

[yy306525121]

@SmiteChow 嗯，也不是为了求最优解，想着只要能拍出来一个满足所有硬性条件的就行，个别老师的上课偏好的话现在还没考虑进去

[yy306525121]

@JohnXeno 好的， 谢谢大佬， 我去看一下

[Firw]

@yy306525121 留个微信，不急的话我摸鱼的时候帮你看看

[yy306525121]

@Firw yy306525121 谢谢大佬

[wangxin3]

OptaPlanner 官方有排课的 demo 吧，看看能不能满足你需求
https://www.optaplanner.org/docs/optaplanner/latest/quickstart/spring-boot/spring-boot-quickstart.html

[chniccs]

看了一下，好多人的老婆是老师呀。

[yy306525121]

@wangxin3 这个看过了， 数据比较大的话计算时间太长了

[yy306525121]

@chniccs 哈哈， 老师多好呀

[luxurine]

https://github.com/SJTU-Plus/course-plus
不知这个是否可以直接用

[juventusryp]

最近也在写一个机房的排课软件，主要就是把需要某门课安排到有这个软件的机房中，然后尽量连着上课，看着简单，写起来头都是大的，借助 AI 磕磕碰碰写的也算能用，蹲个坑看看有没有大佬有更好的解法

[yy306525121]

@juventusryp 用什么算法实现的啊

[Sawyerhou]

看了下 stackflow ，确实有难度。

你这个排课有点像拼魔方，约束条件之间互相干涉。

参考魔方万能公式的思路呢？
将一个格子归位的同时，必须保证其他格子不动。

换到你这里，
解决当前冲突的同时，不能产生新的已经解决过的冲突
直到冲突全部解决。

当然，这种贪心算法说起来容易，能不能写出来就两说 : P

[yy306525121]

感谢 @Firw 大佬，程序已经写出来了，速度还很快， 使用的是 or-tools 的 cp-sat （具体我不太懂，也刚开始学习）， 目前还有一些约束正在和大佬确认中， 已经确认程序可行， 有想要的伙伴们，等所有约束都确认完之后会放到下面的评论中的

[yy306525121]

代码地址： https://raw.githubusercontent.com/yy306525121/school_scheduling/main/plan3.py ， 有感兴趣的大佬们可以去看一下

[wangxin3]

基于 op 的数据和约束，用 OptaPlanner 做了一个 Java 版本，有兴趣的朋友可以看看😁
https://github.com/WangXin3/school_scheduling/

[yy306525121]

@wangxin3 好的大佬有空我试试

[lifeOsDeveloper]

@wangxin3 用你的代码测试了一下，2min 只能跑到 best score (90hard/18soft)， 这种一般要跑多久啊，最终能跑到 0hard 吗

[yy306525121]

@tywtyw2002
@lifeOsDeveloper 这种和我之前用的 timefold 一样，问题规模小的话可以跑，问题规模一大无解，不知道上高性能计算机能不能跑出来，我之前 hard 跑了一夜还是 18 ，想跑到 0 很难

[wangxin3]

@lifeOsDeveloper 是这样的。90hard 是我给加分了，90 来源是因为 1 、2 、6 节必须有课，所以每天每个班需要加三分，一周一个班需要加 18 分，测试数据五个班是加了 90 分，所以在硬约束来说是最优解了。我现在代码有点乱，有加分、有减分。。。