V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yy306525121
V2EX  ›  程序员

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

  •  2
     
  •   yy306525121 · 75 天前 · 9433 次点击
    这是一个创建于 75 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    第 1 条附言  ·  4 天前
    [通过 ortools 实现的 python 版代码已经在评论区贴出]
    135 条回复    2024-09-02 18:17:23 +08:00
    1  2  
    ilovey482i
        1
    ilovey482i  
       75 天前
    排课是非常复杂的,不是一件容易的事
    yy306525121
        2
    yy306525121  
    OP
       75 天前
    @ilovey482i 嗯,是的, 所以才来问问看有没有知道的大佬, 除了 timefold 和遗传算法还有没有其他简单的方式,毕竟也是第一次写排课这种东西。
    SenLief
        3
    SenLief  
       75 天前
    排课很复杂的,我们公司当时砸了不少钱进去,做出来的系统也不尽人意。

    不过如果是高中学校排课,那就简单了。不用程序,因为班级是固定的,只需要排老师就好了。
    billzhuang
        4
    billzhuang  
       75 天前 via iPhone
    OptaPlanner
    yy306525121
        5
    yy306525121  
    OP
       75 天前
    @SenLief 相比大学的应该是简单很多,基本几个条件满足就行了, 我媳妇每次手动排课要不就是解决冲突,要不就是个别老师找她调整,想着正好看能不能写个程序简化一下她的操作。
    cndenis
        6
    cndenis  
       75 天前   ❤️ 1
    随机排, 然后遍历所有条件, 输出符合条件的
    JayZXu
        7
    JayZXu  
       75 天前
    当时隔壁组做个排班要死要活的
    围观学习大佬经验
    yy306525121
        8
    yy306525121  
    OP
       75 天前
    @billzhuang optaplanner 和 timefold 其实是一个东西, 我试了,这东西好像是 NLP 问题, 就像笛卡尔积一样,条件和教师数据量上来之后,要计算的数据量会几何倍暴增,我之前写的只排了高三的课程,结果日志显示数据规模直接干到 3.7xxx 乘以 10 的 256 次方
    raptor
        9
    raptor  
       75 天前
    试试用 AI 排课?
    yy306525121
        10
    yy306525121  
    OP
       75 天前
    @raptor 呃,你说现在的那种聊天式的 AI? 还是有人直接做好的 AI 产品?
    lneoi
        11
    lneoi  
       75 天前
    对这块不了解, 印象中 OR-Tools / PuLP 里求解器好像支持排课场景, 还有一个 MiniZinc 好像比较复杂, 但针对排场排课领域, 可以看看
    forty
        12
    forty  
       75 天前
    输入哪些条件,输出有什么要求,这些需求描述一下?难点是哪里?似乎没有多大运算量
    yy306525121
        13
    yy306525121  
    OP
       75 天前
    @lneoi 好的,谢谢大佬, 之前用过 timefold ,和 or-tool 这些其实是一类工具, 都是问题求解器, 但是他们都是基于一个原理, 把所有可能的组合全部排列出来,然后找出最优解,这种框架会有一个问题, 就是当你的问题或者叫排课里面的教师和班级数量上来之后问题规模会成指数倍增长,家用计算机跑一天都跑不出来,timefold 那个我已经上 overstack 上问了, 还没有人回复我,我先看看你说得其他几个看看有没有什么好的解决方法。
    foxkiller
        14
    foxkiller  
       75 天前
    关键词……遗传算法……
    freemyspace
        15
    freemyspace  
       75 天前
    mark 一下,看下有啥好方法
    yy306525121
        16
    yy306525121  
    OP
       75 天前
    @foxkiller 嗯嗯, 搜到了, 看了一下有点难以理解, 看看有更好的方法不, 没有的话再研究这个
    yy306525121
        17
    yy306525121  
    OP
       75 天前
    @freemyspace 好的
    tywtyw2002
        18
    tywtyw2002  
       75 天前 via iPhone
    高中排课程 没那么复杂吧?

    多少个班级? 多少个科目/多少个任课教师?
    人排的话也就是一个小时的事情。

    也可能是我们班级比较少,老师多吧。

    14 个班级,主科目每天一节,每周 6 节,一个老师三个班。

    其他课程 每周 2 节,一个老师 7 个班级。
    yy306525121
        19
    yy306525121  
    OP
       75 天前
    @tywtyw2002 我们课程没那么固定,每个科目的课程安排都不一样, 而且还有老师跨阶段的情况,其实人排的话唯一的麻烦就是冲突问题不好解决
    yy306525121
        20
    yy306525121  
    OP
       75 天前
    @tywtyw2002 我们 16 个班,但是老师有六十个左右,同阶段不同的班级上的课的科目还不一样😄
    billzhuang
        21
    billzhuang  
       75 天前 via iPhone   ❤️ 1
    OptaPlanner 可以设置一个退出条件,你要的不是最优解,是能接受的解。
    tywtyw2002
        22
    tywtyw2002  
       75 天前 via iPhone
    科目是跟老师走的。
    按照老师去分课程就行了。
    比如说三个语文老师,这三个语文老师可以同时教三个班。

    一般冲突多的是体育老师之类的,他们先拍,然后在排主科老师。
    cocogovern
        23
    cocogovern  
       75 天前
    你用 chatgpt 都比自己编的强。
    yy306525121
        24
    yy306525121  
    OP
       75 天前 via iPhone
    @billzhuang 它有一个 hard 得分和 soft 得分,hard 分数是负的,肯定不行吧,soft 得分倒是无所谓
    yy306525121
        25
    yy306525121  
    OP
       75 天前
    @tywtyw2002 嗯嗯, 好的,谢谢大佬指导
    Sawyerhou
        26
    Sawyerhou  
       75 天前
    建议举个具体的例子,对着具体的需求比较好想算法。

    考虑强化学习,围棋都搞得定,排课的动作空间应该问题不大。
    yy306525121
        27
    yy306525121  
    OP
       75 天前
    @cocogovern gpt 这种倒是没试过
    yy306525121
        28
    yy306525121  
    OP
       75 天前
    @cocogovern 试了 gpt 好像不行,排着排着突然提示我无法进行更高级的数据分析。请稍后再试
    hcocoa
        29
    hcocoa  
       75 天前
    感觉这个和 NBA 每年排比赛差不多,要考虑球队城市距离远近、主客场、球馆占用情况等,可以查一下他们是怎么排的
    justFxxk2060
        30
    justFxxk2060  
       75 天前
    有个北漂程序员回长沙,给媳妇做了个排课系统,后来融了一个亿。
    yy306525121
        31
    yy306525121  
    OP
       75 天前
    @Sawyerhou 嗯,他们的课程安排是固定的,比如指定高三一班的语文课时是 4+2 ,意思就是 4 节普通课, 和 2 节连堂课, 一共 8 节课,4 节普通科可以周一到周四每天排一节,剩下的 2 节连堂课周五一次连堂和周六一次连堂,就是普通课时和连堂课都不能在同一天出现重复,就是因为知识储备太少,不知道该用哪种方法,现在能想到的之后遗传算法😄,感谢大佬指导
    8355
        32
    8355  
       75 天前
    这个叫护士排班问题,有论文写的那种难度,
    这个人工介入更好解决,不要把它看成是一个从研发角度很简单的问题。
    学校上课是有校历的,按照课时要求除一下就好了。
    yy306525121
        33
    yy306525121  
    OP
       75 天前
    @justFxxk2060 牛逼, 羡慕啊
    zhoust
        34
    zhoust  
       75 天前
    搞这么复杂,200 块一年 某达排课。
    yy306525121
        35
    yy306525121  
    OP
       75 天前
    @8355 嗯, 确实这种问题人工更简单,如果实在太复杂程序搞不定的话的话我就只写个简单的检测课程表是否有冲突的脚本就行了,人工排完之后脚本检测一下是否有冲突, 这样更简单一些。
    yy306525121
        36
    yy306525121  
    OP
       75 天前
    @zhoust 😄,我媳妇现在用的无忧,只排了高三的吧,他说全阶段没法一起排,忘记是因为啥了, 每年要三百还是四百块钱 VIP
    wen20
        37
    wen20  
       75 天前
    做过这个需求, 感觉还行啊。 班级 老师 俩个要素 在时间轴上的 占用和冲突检测。
    yqf0215
        38
    yqf0215  
       75 天前
    @zhoust 好奇搜了一下这个某达排课。我以前做过 3/4 年教务,每学期排课累死我了,如果当时知道有这个软件,可能会轻松不少。。。只是不知道功能咋呀
    8355
        39
    8355  
       75 天前
    @yy306525121 #35 之前我们是做客服系统的需求,比你这个还复杂,需要考虑到白班夜班的连续问题,不同等级客服的服务能力问题,全职兼职的工资和性价比问题,客服间的收入平衡问题等等,理想很完美,实际就是没做出来。
    因为人员本身的客观问题系统没办法解决,同时系统的规则需要人员强执行性,由于职业特性流动率就是特别大,很容易把自己搞死了。
    yy306525121
        40
    yy306525121  
    OP
       75 天前
    @yqf0215 你先去试用一下, 好不好用回来反馈一下,哈哈
    yy306525121
        41
    yy306525121  
    OP
       75 天前
    @8355 嗯,这种问题程序确实很难做,我其实也是前前后后拖了一年,我媳妇天天念叨自己排课费劲才又想着看看能不能做一个呢哈哈
    tywtyw2002
        42
    tywtyw2002  
       75 天前
    @yy306525121 #31 你这个连堂课不就是 6+2 嘛

    每天拍一节可,然后找 2 天在这节课前面和后面插一节课就行了。

    rule base 就行了,python 写个一天就能出来了。

    不用上什么强化学习之类的。。。。。

    你手动拍一次课表你就明白 这个排课的逻辑了。
    yy306525121
        43
    yy306525121  
    OP
       75 天前
    @tywtyw2002 我大概好像有点理解你的意思了, 感谢大佬, 我再仔细琢磨一下,
    Volekingsg
        44
    Volekingsg  
       75 天前
    之前帮人写过,直接整数线性规划一把梭了
    guguji5
        45
    guguji5  
       75 天前
    https://console.flashcat.cloud/oncall

    感觉跟我们做的排班一样。
    xuanbg
        46
    xuanbg  
       75 天前
    排课没那么复杂,就是把每个班的周课表排出来,唯一约束是老师的时间不能冲突。周课表就是一个 3 维数组,然后把你有限的对象(老师)一个个放进这个数组就完了。假设 A 老师每周 3 节课,就有对象 T1{"name": "A"}、T2{"name": "A"}、T3{"name": "A"}。如果老师有跨年级跨学科的,就要给老师这个对象加上年级和学科属性,最后排的时候,要求数组在时间维度上,每个对象的每个属性都是唯一的就行。
    aeron
        47
    aeron  
       75 天前
    meeop
        48
    meeop  
       75 天前
    https://genwebapp.com/apps?appId=HhbxiqyFE6HE-USj

    看看 genwebapp.com
    用 ai 帮你写了一个,看看能不能用,不满意还可以让 ai 改
    yy306525121
        49
    yy306525121  
    OP
       75 天前
    @xuanbg 是啊,大脑想起来挺简单的,但是写起来感觉挺难的
    yy306525121
        50
    yy306525121  
    OP
       75 天前
    @aeron 好的,谢谢大佬,我去看看学习一下
    yy306525121
        51
    yy306525121  
    OP
       75 天前
    @meeop 牛哇大佬,我看一下
    yy306525121
        52
    yy306525121  
    OP
       75 天前
    @meeop 能给老师指定班级吗? 例如李四教高三 1 班的语文,并且课程安排是 4+2 这样,4 节普通课时,每天一节,2 次连堂课, 每天一次连堂课
    gegewu0927
        53
    gegewu0927  
       75 天前
    meeop
        54
    meeop  
       75 天前
    @yy306525121 应该可以,不过这种细节修改得你自己让 ai 改拉,试一下吧,开发过程的 prompt 我都截图展示了
    meeop
        55
    meeop  
       75 天前
    @yy306525121 代码的话网页查看源代码,在 html 代码基础上让 ai 改就行
    meeop
        56
    meeop  
       75 天前
    或者干脆重新开发一个,也就几句话的事
    yy306525121
        57
    yy306525121  
    OP
       75 天前
    @gegewu0927 感谢大佬, 我看看
    yy306525121
        58
    yy306525121  
    OP
       75 天前
    @meeop 好的大佬
    Les1ie
        59
    Les1ie  
       75 天前
    很多年以前写过排班的,具体咋写的忘了,好像是固定了一些限定条件之后用最大流算法。随机生成再排除冲突方案大概率是不行的,效率奇低。
    yy306525121
        60
    yy306525121  
    OP
       75 天前
    @Les1ie 是的, 效率太低也不行
    HFX3389
        61
    HFX3389  
       75 天前
    排课不能冲突,而且还有如果老师突然生病、有急事或者希望调课不知道是否又要重新计算
    tywtyw2002
        62
    tywtyw2002  
       75 天前
    @HFX3389 #60 这个不是需求吧。 要调课自己找别的老师去调,实在不行找年级组长。大不了让学生上自习被,高中不都是这么过来的吗
    snylonue
        63
    snylonue  
       75 天前
    就是暴力解方程组吧,指数级的复杂度
    性能不够可以上 hpc
    ZZZZone
        64
    ZZZZone  
       75 天前
    经典护士排班问题+1
    两种思路:
    小范围可以整数规划精确求解 :
    比如 google 开源的 or-tools
    https://developers.google.com/optimization/service/scheduling/nurse_scheduling_example
    范围大的只能求局部最优, 各种搜索算法
    比如推荐看一下: http://scis.scichina.com/cn/2016/N112015-00284.pdf
    SenLief
        65
    SenLief  
       75 天前
    高中属于搭班的,不知道你们那里是不是,如果采用搭班架的形式是很容易排课的。
    chaoxu
        66
    chaoxu  
       75 天前
    @yy306525121 "和 or-tool 这些其实是一类工具, 都是问题求解器, 但是他们都是基于一个原理, 把所有可能的组合全部排列出来,然后找出最优解,这种框架会有一个问题, 就是当你的问题或者叫排课里面的教师和班级数量上来之后问题规模会成指数倍增长,家用计算机跑一天都跑不出来"

    不是把所有组合排列出来,会有大量的剪枝操作。一般人自己写的系统是比不过的。

    你整个帖子都没有一个正确的数学上的描述。只要能描述出来,就能找做运筹的人写出来。
    Huelse
        67
    Huelse  
       75 天前
    我之前设计的排课系统就是按周循环的排列组合,一个老师在一个时间上的课为一个单位,多个老师组合即可。
    LaurelHarmon
        68
    LaurelHarmon  
       75 天前
    这应该是个刚需,难道没有成熟解决方案吗?
    这种问题暴力搜索肯定不可取,代码怎么写不重要,算法才是关键,需要专业的复杂度优化策略,自己鼓捣性价比太低。
    还是好好挣钱吧,有这时间多赚点钱,让老婆冲个 VIP 就解决了,手搓不可取,个人意见
    w16311
        69
    w16311  
       75 天前
    整数规划问题,可以试试匈牙利算法,多项式复杂度。OP 最好还是用现成的,这个自己写不值当,算法上几乎不可能有提升,做到无非是把业务给的数据变成算法输入的数据。
    zjb861107488
        70
    zjb861107488  
       75 天前 via iPhone   ❤️ 2
    我爸是高中数学老师,之前上学的时候看他排过。先用数学这一科去排,把各种复杂因素都考虑进去。然后语文、外语等,最后用副科做填空题。
    记得当时不到 20 个班级半天就排好了,然后看有特殊需要照顾的(比如刚生完小孩需要早点下班)的微调一下。不要追求满足所有人的需求,有要调整的老师们可以私下换课,或者改成周末、晚自习。
    HFX3389
        71
    HFX3389  
       75 天前
    @tywtyw2002 #62 只是有这个想法,万一老师想全部在系统上搞定,让学生以系统的课时上课为准,或者说未来计算课时费等场景时以排课系统为准的话,就会有这种情况。

    甚至于老师突发请产假,调休,突发外派到其他地方几个星期等等。

    不然校领导一句话“你这系统是死的呀,灵活度不够啊,只适合开学前用一次然后导出 Excel 表再贴到在线文档就足够了,没有持续使用的必要”,那就真成义务劳动了
    yy306525121
        72
    yy306525121  
    OP
       75 天前
    @ZZZZone 好的,谢谢大佬
    yy306525121
        73
    yy306525121  
    OP
       75 天前
    @HFX3389 对,其实我媳妇他们学校现在就是按照课表上的来算课时的,有临时调整的话算玩之后再在 excel 表里面加减
    yy306525121
        74
    yy306525121  
    OP
       75 天前
    @w16311 谢谢大佬给的思路,我去看一下
    yy306525121
        75
    yy306525121  
    OP
       75 天前
    @LaurelHarmon 嗯嗯, 这是最终解决方案了, 手搓不出来就只能去冲 vip 了
    xiaogu2014
        76
    xiaogu2014  
       75 天前
    如果熟悉 gurobi 的话可以用这个来做计算。高性能来解决优化问题的。
    比如这个例子:
    https://github.com/carloalbe/A-nurse-scheduling-problem-solved-with-Gurobi
    cxsz
        77
    cxsz  
       75 天前
    围观一下,买过 水晶排课 的会员
    yy306525121
        78
    yy306525121  
    OP
       75 天前
    @xiaogu2014 这个好像也是问题求解器的一种,和 or-tools 和 timefold 一样的东西, 但是好像是收费的, 可以用我妹妹的学生申请一个资格试试😄
    yy306525121
        79
    yy306525121  
    OP
       75 天前
    @cxsz 好用吗?
    cxsz
        80
    cxsz  
       75 天前
    @yy306525121 #79 用来排初中课程的,感觉还行,整体先出一版,然后特殊情况手动调整
    yy306525121
        81
    yy306525121  
    OP
       75 天前
    感谢大佬们, 我应该已经有了思路了,我先去写写, 看看能搞出来不
    Y25tIGxpdmlk
        82
    Y25tIGxpdmlk  
       74 天前
    @zjb861107488 #70 对,先大概排好,发一个预告版,然后让老师们自己去发现细节问题,然后自己互相微调。
    Alastar
        83
    Alastar  
       74 天前
    需要走班排课逻辑么?可以提供一些思路
    freemyspace
        84
    freemyspace  
       74 天前
    大佬写出来了记得通知我一声
    p1gd0g
        85
    p1gd0g  
       74 天前
    还以为这种问题有很成熟通用的方案了,蹲个后续
    zjhzxhz
        86
    zjhzxhz  
       74 天前   ❤️ 1
    @yy306525121 #8 大哥,你说的应该是 NP ,不是 NLP 。
    wuhaisen
        87
    wuhaisen  
       74 天前
    @yy306525121 #81 大佬,搞出来记得分享一下
    yy306525121
        88
    yy306525121  
    OP
       74 天前
    @zjhzxhz 对 NP,哈哈
    yy306525121
        89
    yy306525121  
    OP
       74 天前
    @wuhaisen 又不知道怎么搞了, 唉, 我再好好想想吧
    xscc
        90
    xscc  
       74 天前
    网上翻了下,有很多成品,让学校花点小钱买一个吧,正常情况下你做不到他们那么专业
    hiveex
        91
    hiveex  
       74 天前
    之前我也想为老婆手搓一个 写了两天放弃了 太复杂而且教师需求不一 烦躁
    yy306525121
        92
    yy306525121  
    OP
       74 天前
    @hiveex 是啊, 烦啊
    FightPig
        93
    FightPig  
       74 天前
    有成品用成品吧,自己写太麻烦了
    SmiteChow
        94
    SmiteChow  
       74 天前
    这个要看权力,你老婆有权拍板怎么排都行,反之约束越多越不行可能就没有可行解了。

    通常来讲做成人力资源桶初期随机抽取算出一个可行解就行了,而不是去求解最优解。

    最优解一般是人私底下调课的范畴。
    SOSdanOffical
        95
    SOSdanOffical  
       74 天前 via iPhone
    现在当老师都得会这么高端的技能了么
    或者换个问题,如果不需要会,为什么要上杆子给学校省钱,该找外包开发就找嘛
    Firw
        96
    Firw  
       74 天前
    楼都看了一遍,还是有几个兄弟懂运筹优化的。这个问题建好模型丢给求解器就行了,不如把具体的决策变量、约束条件、目标函数大概讲出来,自然有大佬摸鱼的时候帮你建模求解。另外你提到的求解器效率不行,模型建的好不好会直接影响求解效率,一些建模技巧你可能不了解没有用到。
    JohnXeno
        97
    JohnXeno  
       74 天前
    IBM ILOG CPLEX Optimization Studio , 里面的功能还挺全的, 尤其是做组合优化问题或者需要满足复杂约束的时候, 之前帮同学做医生的排班表用的这个, 不过上手有点难度, 而且需要你自己有一定的数学抽象能力
    JohnXeno
        98
    JohnXeno  
       74 天前
    python 里面应该也有一些类似 IBM ILOG CPLEX Optimization Studio 的开源库, 你可以去搜一下, 条件约束可以你自己描述然后扔给大模型去写
    iosx
        99
    iosx  
       74 天前
    巧了,上午再查排课算法。搜到了这个,https://paike.yunxiao.com/ 你试试(非广告)
    volvo007
        100
    volvo007  
       74 天前
    @yy306525121 你要用 gpt 去搞定 遗传算法问题,不是直接用 gpt 去算啊…… 会 py 的话有现成的库可以调用,条件设好应该挺快的
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5351 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 05:46 · PVG 13:46 · LAX 21:46 · JFK 00:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.