这是一个创建于 103 天前的主题，其中的信息可能已经有所发展或是发生改变。
因为媳妇高中需要排课，享用程序给她写一个， 之前试了 timefold ，写出来之后由于规模太大， 两三个老师还能拍出来，数量一多之后连着跑了一两天也没跑出来，想问一下，除了 timefold 这种问题求解器之外， 还有什么简单的方法做这种排课程序，遗传算法是不是最简单的方式？
第 1 条附言 · 33 天前
[通过 ortools 实现的 python 版代码已经在评论区贴出]
第 2 条附言 · 33 天前
135 条回复 • 2024-09-02 18:17:23 +08:00
 |
1
ilovey482i 103 天前
排课是非常复杂的，不是一件容易的事
|
 |
2
yy306525121 OP @ilovey482i 嗯，是的， 所以才来问问看有没有知道的大佬， 除了 timefold 和遗传算法还有没有其他简单的方式，毕竟也是第一次写排课这种东西。
|
 |
3
SenLief 103 天前
排课很复杂的，我们公司当时砸了不少钱进去，做出来的系统也不尽人意。
不过如果是高中学校排课，那就简单了。不用程序，因为班级是固定的，只需要排老师就好了。 |
 |
4
billzhuang 103 天前 via iPhone
OptaPlanner
|
|
5
yy306525121 OP @SenLief 相比大学的应该是简单很多，基本几个条件满足就行了， 我媳妇每次手动排课要不就是解决冲突，要不就是个别老师找她调整，想着正好看能不能写个程序简化一下她的操作。
|
 |
6
cndenis 103 天前  1
随机排, 然后遍历所有条件, 输出符合条件的
|
 |
7
JayZXu 103 天前
当时隔壁组做个排班要死要活的
围观学习大佬经验 |
|
8
yy306525121 OP @billzhuang optaplanner 和 timefold 其实是一个东西， 我试了，这东西好像是 NLP 问题， 就像笛卡尔积一样，条件和教师数据量上来之后，要计算的数据量会几何倍暴增，我之前写的只排了高三的课程，结果日志显示数据规模直接干到 3.7xxx 乘以 10 的 256 次方
|
 |
9
raptor 103 天前
试试用 AI 排课？
|
|
10
yy306525121 OP @raptor 呃，你说现在的那种聊天式的 AI? 还是有人直接做好的 AI 产品？
|
 |
11
lneoi 103 天前
对这块不了解, 印象中 OR-Tools / PuLP 里求解器好像支持排课场景, 还有一个 MiniZinc 好像比较复杂, 但针对排场排课领域, 可以看看
|
 |
12
forty 103 天前
输入哪些条件，输出有什么要求，这些需求描述一下？难点是哪里？似乎没有多大运算量
|
|
13
yy306525121 OP @lneoi 好的，谢谢大佬， 之前用过 timefold ，和 or-tool 这些其实是一类工具， 都是问题求解器， 但是他们都是基于一个原理， 把所有可能的组合全部排列出来，然后找出最优解，这种框架会有一个问题， 就是当你的问题或者叫排课里面的教师和班级数量上来之后问题规模会成指数倍增长，家用计算机跑一天都跑不出来，timefold 那个我已经上 overstack 上问了， 还没有人回复我，我先看看你说得其他几个看看有没有什么好的解决方法。
|
 |
14
foxkiller 103 天前
关键词……遗传算法……
|
 |
15
freemyspace 103 天前
mark 一下，看下有啥好方法
|
|
16
yy306525121 OP @foxkiller 嗯嗯， 搜到了， 看了一下有点难以理解， 看看有更好的方法不， 没有的话再研究这个
|
|
17
yy306525121 OP @freemyspace 好的
|
 |
18
tywtyw2002 103 天前 via iPhone
高中排课程 没那么复杂吧？
多少个班级？ 多少个科目/多少个任课教师？ 人排的话也就是一个小时的事情。 也可能是我们班级比较少，老师多吧。 14 个班级，主科目每天一节，每周 6 节，一个老师三个班。 其他课程 每周 2 节，一个老师 7 个班级。 |
|
19
yy306525121 OP @tywtyw2002 我们课程没那么固定，每个科目的课程安排都不一样， 而且还有老师跨阶段的情况，其实人排的话唯一的麻烦就是冲突问题不好解决
|
|
20
yy306525121 OP @tywtyw2002 我们 16 个班，但是老师有六十个左右，同阶段不同的班级上的课的科目还不一样😄
|
|
21
billzhuang 103 天前 via iPhone 1
OptaPlanner 可以设置一个退出条件，你要的不是最优解，是能接受的解。
|
|
22
tywtyw2002 103 天前 via iPhone
科目是跟老师走的。
按照老师去分课程就行了。 比如说三个语文老师，这三个语文老师可以同时教三个班。 一般冲突多的是体育老师之类的，他们先拍，然后在排主科老师。 |
 |
23
cocogovern 103 天前
你用 chatgpt 都比自己编的强。
|
|
24
yy306525121 OP @billzhuang 它有一个 hard 得分和 soft 得分，hard 分数是负的，肯定不行吧，soft 得分倒是无所谓
|
|
25
yy306525121 OP @tywtyw2002 嗯嗯， 好的，谢谢大佬指导
|
 |
26
Sawyerhou 103 天前
建议举个具体的例子，对着具体的需求比较好想算法。
考虑强化学习，围棋都搞得定，排课的动作空间应该问题不大。 |
|
27
yy306525121 OP @cocogovern gpt 这种倒是没试过
|
|
28
yy306525121 OP @cocogovern 试了 gpt 好像不行，排着排着突然提示我无法进行更高级的数据分析。请稍后再试
|
 |
29
hcocoa 103 天前
感觉这个和 NBA 每年排比赛差不多，要考虑球队城市距离远近、主客场、球馆占用情况等，可以查一下他们是怎么排的
|
 |
30
justFxxk2060 103 天前
有个北漂程序员回长沙，给媳妇做了个排课系统，后来融了一个亿。
|
|
31
yy306525121 OP @Sawyerhou 嗯，他们的课程安排是固定的，比如指定高三一班的语文课时是 4+2 ，意思就是 4 节普通课， 和 2 节连堂课， 一共 8 节课，4 节普通科可以周一到周四每天排一节，剩下的 2 节连堂课周五一次连堂和周六一次连堂，就是普通课时和连堂课都不能在同一天出现重复，就是因为知识储备太少，不知道该用哪种方法，现在能想到的之后遗传算法😄，感谢大佬指导
|
 |
32
8355 103 天前
这个叫护士排班问题，有论文写的那种难度，
这个人工介入更好解决，不要把它看成是一个从研发角度很简单的问题。 学校上课是有校历的，按照课时要求除一下就好了。 |
|
33
yy306525121 OP @justFxxk2060 牛逼， 羡慕啊
|
 |
34
zhoust 103 天前
搞这么复杂，200 块一年 某达排课。
|
|
35
yy306525121 OP @8355 嗯， 确实这种问题人工更简单，如果实在太复杂程序搞不定的话的话我就只写个简单的检测课程表是否有冲突的脚本就行了，人工排完之后脚本检测一下是否有冲突， 这样更简单一些。
|
|
36
yy306525121 OP @zhoust 😄，我媳妇现在用的无忧，只排了高三的吧，他说全阶段没法一起排，忘记是因为啥了， 每年要三百还是四百块钱 VIP
|
 |
37
wen20 103 天前
做过这个需求， 感觉还行啊。 班级 老师 俩个要素 在时间轴上的 占用和冲突检测。
|
|
39
8355 103 天前
@yy306525121 #35 之前我们是做客服系统的需求，比你这个还复杂，需要考虑到白班夜班的连续问题，不同等级客服的服务能力问题，全职兼职的工资和性价比问题，客服间的收入平衡问题等等，理想很完美，实际就是没做出来。
因为人员本身的客观问题系统没办法解决，同时系统的规则需要人员强执行性，由于职业特性流动率就是特别大，很容易把自己搞死了。 |
|
40
yy306525121 OP @yqf0215 你先去试用一下， 好不好用回来反馈一下，哈哈
|
|
41
yy306525121 OP @8355 嗯，这种问题程序确实很难做，我其实也是前前后后拖了一年，我媳妇天天念叨自己排课费劲才又想着看看能不能做一个呢哈哈
|
|
42
tywtyw2002 103 天前
@yy306525121 #31 你这个连堂课不就是 6+2 嘛
每天拍一节可，然后找 2 天在这节课前面和后面插一节课就行了。 rule base 就行了，python 写个一天就能出来了。 不用上什么强化学习之类的。。。。。 你手动拍一次课表你就明白 这个排课的逻辑了。 |
|
43
yy306525121 OP @tywtyw2002 我大概好像有点理解你的意思了， 感谢大佬， 我再仔细琢磨一下，
|
 |
44
Volekingsg 103 天前
之前帮人写过，直接整数线性规划一把梭了
|
 |
45
guguji5 103 天前
https://console.flashcat.cloud/oncall
感觉跟我们做的排班一样。  |
 |
46
xuanbg 103 天前
排课没那么复杂，就是把每个班的周课表排出来，唯一约束是老师的时间不能冲突。周课表就是一个 3 维数组，然后把你有限的对象（老师）一个个放进这个数组就完了。假设 A 老师每周 3 节课，就有对象 T1{"name": "A"}、T2{"name": "A"}、T3{"name": "A"}。如果老师有跨年级跨学科的，就要给老师这个对象加上年级和学科属性，最后排的时候，要求数组在时间维度上，每个对象的每个属性都是唯一的就行。
|
 |
47
aeron 103 天前
or-tools ，参考一下这个链接试试，https://developers.google.com/optimization/scheduling/employee_scheduling?hl=zh-cn
|
 |
48
meeop 103 天前
|
|
49
yy306525121 OP @xuanbg 是啊，大脑想起来挺简单的，但是写起来感觉挺难的
|
|
50
yy306525121 OP @aeron 好的，谢谢大佬，我去看看学习一下
|
|
51
yy306525121 OP @meeop 牛哇大佬，我看一下
|
|
52
yy306525121 OP @meeop 能给老师指定班级吗？ 例如李四教高三 1 班的语文，并且课程安排是 4+2 这样，4 节普通课时，每天一节，2 次连堂课， 每天一次连堂课
|
 |
53
gegewu0927 103 天前
|
|
54
meeop 103 天前
@yy306525121 应该可以，不过这种细节修改得你自己让 ai 改拉，试一下吧，开发过程的 prompt 我都截图展示了
|
|
55
meeop 103 天前
@yy306525121 代码的话网页查看源代码，在 html 代码基础上让 ai 改就行
|
|
56
meeop 103 天前
或者干脆重新开发一个，也就几句话的事
|
|
57
yy306525121 OP @gegewu0927 感谢大佬， 我看看
|
|
58
yy306525121 OP @meeop 好的大佬
|
 |
59
Les1ie 103 天前
很多年以前写过排班的，具体咋写的忘了，好像是固定了一些限定条件之后用最大流算法。随机生成再排除冲突方案大概率是不行的，效率奇低。
|
|
60
yy306525121 OP @Les1ie 是的， 效率太低也不行
|
 |
61
HFX3389 103 天前
排课不能冲突，而且还有如果老师突然生病、有急事或者希望调课不知道是否又要重新计算
|
|
62
tywtyw2002 103 天前
@HFX3389 #60 这个不是需求吧。 要调课自己找别的老师去调，实在不行找年级组长。大不了让学生上自习被，高中不都是这么过来的吗
|
 |
63
snylonue 103 天前
就是暴力解方程组吧，指数级的复杂度
性能不够可以上 hpc |
 |
64
ZZZZone 103 天前
经典护士排班问题+1
两种思路： 小范围可以整数规划精确求解 ： 比如 google 开源的 or-tools https://developers.google.com/optimization/service/scheduling/nurse_scheduling_example 范围大的只能求局部最优， 各种搜索算法 比如推荐看一下： http://scis.scichina.com/cn/2016/N112015-00284.pdf |
|
65
SenLief 103 天前
高中属于搭班的，不知道你们那里是不是，如果采用搭班架的形式是很容易排课的。
|
 |
66
chaoxu 103 天前
@yy306525121 "和 or-tool 这些其实是一类工具， 都是问题求解器， 但是他们都是基于一个原理， 把所有可能的组合全部排列出来，然后找出最优解，这种框架会有一个问题， 就是当你的问题或者叫排课里面的教师和班级数量上来之后问题规模会成指数倍增长，家用计算机跑一天都跑不出来"
不是把所有组合排列出来，会有大量的剪枝操作。一般人自己写的系统是比不过的。 你整个帖子都没有一个正确的数学上的描述。只要能描述出来，就能找做运筹的人写出来。 |
 |
67
Huelse 103 天前
我之前设计的排课系统就是按周循环的排列组合，一个老师在一个时间上的课为一个单位，多个老师组合即可。
|
 |
68
LaurelHarmon 103 天前
这应该是个刚需，难道没有成熟解决方案吗？
这种问题暴力搜索肯定不可取，代码怎么写不重要，算法才是关键，需要专业的复杂度优化策略，自己鼓捣性价比太低。 还是好好挣钱吧，有这时间多赚点钱，让老婆冲个 VIP 就解决了，手搓不可取，个人意见 |
 |
69
w16311 103 天前
整数规划问题，可以试试匈牙利算法，多项式复杂度。OP 最好还是用现成的，这个自己写不值当，算法上几乎不可能有提升，做到无非是把业务给的数据变成算法输入的数据。
|
 |
70
zjb861107488 103 天前 via iPhone 2
我爸是高中数学老师，之前上学的时候看他排过。先用数学这一科去排，把各种复杂因素都考虑进去。然后语文、外语等，最后用副科做填空题。
记得当时不到 20 个班级半天就排好了，然后看有特殊需要照顾的（比如刚生完小孩需要早点下班）的微调一下。不要追求满足所有人的需求，有要调整的老师们可以私下换课，或者改成周末、晚自习。 |
|
71
HFX3389 103 天前
@tywtyw2002 #62 只是有这个想法，万一老师想全部在系统上搞定，让学生以系统的课时上课为准，或者说未来计算课时费等场景时以排课系统为准的话，就会有这种情况。
甚至于老师突发请产假，调休，突发外派到其他地方几个星期等等。 不然校领导一句话“你这系统是死的呀，灵活度不够啊，只适合开学前用一次然后导出 Excel 表再贴到在线文档就足够了，没有持续使用的必要”，那就真成义务劳动了 |
|
72
yy306525121 OP @ZZZZone 好的，谢谢大佬
|
|
73
yy306525121 OP @HFX3389 对，其实我媳妇他们学校现在就是按照课表上的来算课时的，有临时调整的话算玩之后再在 excel 表里面加减
|
|
74
yy306525121 OP @w16311 谢谢大佬给的思路，我去看一下
|
|
75
yy306525121 OP @LaurelHarmon 嗯嗯， 这是最终解决方案了， 手搓不出来就只能去冲 vip 了
|
 |
76
xiaogu2014 103 天前
如果熟悉 gurobi 的话可以用这个来做计算。高性能来解决优化问题的。
比如这个例子: https://github.com/carloalbe/A-nurse-scheduling-problem-solved-with-Gurobi |
 |
77
cxsz 103 天前
围观一下，买过 水晶排课 的会员
|
|
78
yy306525121 OP @xiaogu2014 这个好像也是问题求解器的一种，和 or-tools 和 timefold 一样的东西， 但是好像是收费的， 可以用我妹妹的学生申请一个资格试试😄
|
|
79
yy306525121 OP @cxsz 好用吗？
|
|
80
cxsz 103 天前
@yy306525121 #79 用来排初中课程的，感觉还行，整体先出一版，然后特殊情况手动调整
|
|
81
yy306525121 OP 感谢大佬们， 我应该已经有了思路了，我先去写写， 看看能搞出来不
|
 |
82
Y25tIGxpdmlk 103 天前
@zjb861107488 #70 对，先大概排好，发一个预告版，然后让老师们自己去发现细节问题，然后自己互相微调。
|
 |
83
Alastar 103 天前
需要走班排课逻辑么？可以提供一些思路
|
|
84
freemyspace 103 天前
大佬写出来了记得通知我一声
|
 |
85
p1gd0g 103 天前
还以为这种问题有很成熟通用的方案了，蹲个后续
|
 |
86
zjhzxhz 103 天前 1
@yy306525121 #8 大哥，你说的应该是 NP ，不是 NLP 。
|
 |
87
wuhaisen 103 天前
@yy306525121 #81 大佬，搞出来记得分享一下
|
|
88
yy306525121 OP @zjhzxhz 对 NP,哈哈
|
|
89
yy306525121 OP @wuhaisen 又不知道怎么搞了， 唉， 我再好好想想吧
|
 |
90
xscc 103 天前
网上翻了下，有很多成品，让学校花点小钱买一个吧，正常情况下你做不到他们那么专业
|
 |
91
hiveex 103 天前
之前我也想为老婆手搓一个 写了两天放弃了 太复杂而且教师需求不一 烦躁
|
|
92
yy306525121 OP @hiveex 是啊， 烦啊
|
 |
93
FightPig 103 天前
有成品用成品吧，自己写太麻烦了
|
 |
94
SmiteChow 103 天前
这个要看权力，你老婆有权拍板怎么排都行，反之约束越多越不行可能就没有可行解了。
通常来讲做成人力资源桶初期随机抽取算出一个可行解就行了，而不是去求解最优解。 最优解一般是人私底下调课的范畴。 |
 |
95
SOSdanOffical 103 天前 via iPhone
现在当老师都得会这么高端的技能了么
或者换个问题，如果不需要会，为什么要上杆子给学校省钱，该找外包开发就找嘛 |
 |
96
Firw 103 天前
楼都看了一遍，还是有几个兄弟懂运筹优化的。这个问题建好模型丢给求解器就行了，不如把具体的决策变量、约束条件、目标函数大概讲出来，自然有大佬摸鱼的时候帮你建模求解。另外你提到的求解器效率不行，模型建的好不好会直接影响求解效率，一些建模技巧你可能不了解没有用到。
|
 |
97
JohnXeno 103 天前
IBM ILOG CPLEX Optimization Studio , 里面的功能还挺全的, 尤其是做组合优化问题或者需要满足复杂约束的时候, 之前帮同学做医生的排班表用的这个, 不过上手有点难度, 而且需要你自己有一定的数学抽象能力
|
|
98
JohnXeno 103 天前
python 里面应该也有一些类似 IBM ILOG CPLEX Optimization Studio 的开源库, 你可以去搜一下, 条件约束可以你自己描述然后扔给大模型去写
|
 |
99
iosx 103 天前
巧了，上午再查排课算法。搜到了这个，https://paike.yunxiao.com/ 你试试（非广告）
|
 |
100
volvo007 103 天前
@yy306525121 你要用 gpt 去搞定 遗传算法问题，不是直接用 gpt 去算啊…… 会 py 的话有现成的库可以调用，条件设好应该挺快的
|
Select Language