因为媳妇高中需要排课，享用程序给她写一个， 之前试了 timefold ，写出来之后由于规模太大， 两三个老师还能拍出来，数量一多之后连着跑了一两天也没跑出来，想问一下，除了 timefold 这种问题求解器之外， 还有什么简单的方法做这种排课程序，遗传算法是不是最简单的方式？
135 条回复 • 2024-09-02 18:17:23 +08:00
 |
101
lxdlam 28 天前  1
一个 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 |
 |
102
Pteromyini 28 天前
据我所知排课问题是典型的 NP-Hard 问题，不过要是单纯的想得到一个解而不是最优解还是不难，贪心或者局部贪心应该能得到一个解，遗传算法也能得到解
|
 |
103
yqf0215 28 天前
@yy306525121 08 年之后就不在教务处了，到其他部门了
|
 |
104
sindri 28 天前
做过教务，排过课，都是人工来干的。
找过网上收费的，也不贵，几百上千都有。试用一下，速度有点慢，限制真的多。一看就不像是专业人员设计的。 也想过自己做，用 python ，后来实力不允许，加上辞工，不了了之 是个痛，关注一下 UP 主的进度。 |
 |
105
dingyaguang117 27 天前
搜索 + 剪枝 可能效率高很多
|
|
106
dingyaguang117 27 天前
原来这么大市场，突然间很感兴趣
|
 |
107
klo424 27 天前
看了一下，楼上基本都是云玩家。没真正做过排课的，不会知道他有多复杂。
op 可以参考我之前的一个贴子，https://www.v2ex.com/t/877476 。 虽然我做出来一个简单的排课系统，但是实际用起来还是需要一些人工处理，也是自己学艺不精，对算法研究不够，照市面上成熟的排课系统差远了。 提供个思路吧，可以搜索一下相关专利和论文，排课对算法的理解还是很高的，所以还是得从算法入手才能更好地实现。 |
 |
108
yy306525121 OP @klo424 嗯， 我的算法也不是特别好， 之前都是直接用问题求解器建模扔给求解器的， 但是就是 NP 问题，求解问题的规模太大了。
|
|
109
yy306525121 OP @lxdlam 哈哈， 老哥牛逼
|
|
110
yy306525121 OP @dingyaguang117 好的， 相关算法我得再去学一下
|
|
111
yy306525121 OP @sindri 嗯，开个 VIP 是直接省事， 但是每个学校都有自己的个性化需要处理， 网上的不太好找全部满足的， 我这个排课也不是必须要做出来， 现在很多工作都是我媳妇自己做的， 我现在是空闲时间比较多， 加上这个工作学校每个月多给我媳妇补贴了一千五，我想着能利用我的空闲时间帮我媳妇省点功夫也挺好的。哈哈
|
|
112
yy306525121 OP @Pteromyini 可能是我对问题求解器用的还不够熟练，我也是写这个排课的时候现学的问题求解器，但是写出来的硬性约束太多了，能省的都省了，还是很慢，唉
|
|
113
yy306525121 OP @iosx 好的， 感谢大佬
|
|
114
yy306525121 OP @Firw 很有可能，我也是写这个排课的时候现学的问题求解器
|
|
115
yy306525121 OP @volvo007 好的，我好好研究这个遗传算法， 看看能不能用这个算法解决。
|
|
116
yy306525121 OP 这个是之前使用 timefold （类似 optaplanner 的东西）排课的建模，并且遇到的问题的描述，感兴趣并且有时间的大佬可以抽空帮忙看看，是我哪里写的有问题吗
https://stackoverflow.com/questions/78886785/school-timetable-cant-get-result-within-a-certain-period-of-time |
|
117
yy306525121 OP @SmiteChow 嗯，也不是为了求最优解，想着只要能拍出来一个满足所有硬性条件的就行，个别老师的上课偏好的话现在还没考虑进去
|
|
118
yy306525121 OP @JohnXeno 好的， 谢谢大佬， 我去看一下
|
 |
119
Firw 27 天前
@yy306525121 留个微信，不急的话我摸鱼的时候帮你看看
|
|
120
yy306525121 OP @Firw yy306525121 谢谢大佬
|
 |
121
wangxin3 27 天前
OptaPlanner 官方有排课的 demo 吧，看看能不能满足你需求
https://www.optaplanner.org/docs/optaplanner/latest/quickstart/spring-boot/spring-boot-quickstart.html |
 |
122
chniccs 27 天前
看了一下，好多人的老婆是老师呀。
|
|
123
yy306525121 OP @wangxin3 这个看过了， 数据比较大的话计算时间太长了
|
|
124
yy306525121 OP @chniccs 哈哈， 老师多好呀
|
 |
125
luxurine 27 天前
https://github.com/SJTU-Plus/course-plus
不知这个是否可以直接用 |
 |
126
juventusryp 27 天前
最近也在写一个机房的排课软件，主要就是把需要某门课安排到有这个软件的机房中，然后尽量连着上课，看着简单，写起来头都是大的，借助 AI 磕磕碰碰写的也算能用，蹲个坑看看有没有大佬有更好的解法
|
|
127
yy306525121 OP @juventusryp 用什么算法实现的啊
|
 |
128
Sawyerhou 27 天前
看了下 stackflow ，确实有难度。
你这个排课有点像拼魔方，约束条件之间互相干涉。 参考魔方万能公式的思路呢？ 将一个格子归位的同时，必须保证其他格子不动。 换到你这里， 解决当前冲突的同时，不能产生新的已经解决过的冲突 直到冲突全部解决。 当然，这种贪心算法说起来容易，能不能写出来就两说 : P |
|
129
yy306525121 OP 1
感谢 @Firw 大佬，程序已经写出来了，速度还很快， 使用的是 or-tools 的 cp-sat （具体我不太懂，也刚开始学习）， 目前还有一些约束正在和大佬确认中， 已经确认程序可行， 有想要的伙伴们，等所有约束都确认完之后会放到下面的评论中的
|
|
130
yy306525121 OP 代码地址： https://raw.githubusercontent.com/yy306525121/school_scheduling/main/plan3.py ， 有感兴趣的大佬们可以去看一下
|
|
131
wangxin3 19 天前
基于 op 的数据和约束，用 OptaPlanner 做了一个 Java 版本，有兴趣的朋友可以看看😁
https://github.com/WangXin3/school_scheduling/ |
|
132
yy306525121 OP @wangxin3 好的大佬有空我试试
|
 |
133
lifeOsDeveloper 17 天前
@wangxin3 用你的代码测试了一下，2min 只能跑到 best score (90hard/18soft)， 这种一般要跑多久啊，最终能跑到 0hard 吗
|
|
134
yy306525121 OP @tywtyw2002
@lifeOsDeveloper 这种和我之前用的 timefold 一样，问题规模小的话可以跑，问题规模一大无解，不知道上高性能计算机能不能跑出来，我之前 hard 跑了一夜还是 18 ，想跑到 0 很难 |
|
135
wangxin3 17 天前
@lifeOsDeveloper 是这样的。90hard 是我给加分了，90 来源是因为 1 、2 、6 节必须有课，所以每天每个班需要加三分，一周一个班需要加 18 分，测试数据五个班是加了 90 分，所以在硬约束来说是最优解了。我现在代码有点乱，有加分、有减分。。。
|
Select Language