0. 简述

0.1 生成的课表

生成班级的课表（老师名字用 teacher_X 代替，保护隐私）：

生成老师的课表（老师名字用 teacher_X 代替，保护隐私）：

0.2 实现的功能

1 建模

基于基本信息
- 如班级信息、学科信息、每教师负责的学科和班级
附加各种约束
- 排课的基本约束
  - 每班每时间至多上一节课
  - 每老师每时间至多上一节课
- 排课的定制化约束
  - 各方向（物理/历史）的班级的早自习/正课/晚自习课数量要求
  - 每班而言，部分科目的时间集要求
  - 特殊课程，如单周口语需要对应于双周英语，且全校仅一名口语教师
  - 每班而言，语数外每天正课必须至少一节
  - 每班而言，语数外以外其他课程每天正课至多一节
  - 每班而言，每天每科晚自习至多两节
  - 每班而言，任意课程在正课和晚自习中如果有两节需要连续
  - 每周每科目教研时间不上课。
  - 负责行政的老师周五下午不上课
  - 如果下午是教研会晚上一不安排晚自习
  - 等等（且作为分享展示，删了一些个人用到的很定制的约束，避免展示太繁杂）
再加对好方案的目标定义（不强制约束，但尽量做到）
- 尽量让老师有机会休息半天或全天（课尽量集中在上午、下午、晚上各区间内，尽量少跨，要跨也挨着区间跨）
- 老师的需要在学校工作的时段总数尽量少，特别是晚自习要少，更特别是周天的晚自习尽量少
- 等等（且作为分享展示，删了一些个人用到的很定制的目标，避免展示太繁杂）

2 求解用 OR-Tools 对模型进行求解和优化

3 输出到 Excel

0.2 代码

Python实现年级排课和优化-代码

代码有点长，单独放一篇文章

0.3 Github工程和相关文件

Github 完整工程 :https://github.com/Raytto/ClassSchedule

各文件作用

文件	说明
course_save_var_31499.json	之前结果的保存文件，用以给下次求解提供hint（虽然好像没啥用）可以不用，运行时可注释掉求解前AddHint那部分代码
sample_class.xlsx	课表格式模版。 python输出的时候基于此排版去仅复制sheet和修改单元格值进而输出班级和老师课表（相关代码见最后部分）
solver_ortools_replaced.html	个人是用jupyterlab编辑的，这是生成的网页版（为了隐私，已将原版内部所有老师名字用”teacher_X”代替）
solver_ortools_replaced.ipynb	个人是用jupyterlab编辑的，这是原jupyter文件（为了隐私，已将原版内部所有老师名字用”teacher_X”代替）
solver_ortools_replaced.py	个人是用jupyterlab编辑的，这是生成的py文件（为了隐私，已将原版内部所有老师名字用”teacher_X”代替）

1 出发点

老婆有排课需要。且用代码解决排课脑补比较有意思，就研究了几天。

和手动排课相比

排课本身工作量很大：老婆所在年级有50多个老师、10个班、每班每天早自习到晚自习14节课，周六还上半天，总共大概要排700多节课。
手排费时费力，且质量非常差（老师课程散，容易需要在学校从早耗到晚，之类的）。
且手排每次修改很麻烦，牵一发动全身。

而计算机似乎很适合干这种苦力活。

网上有一些排课软件，但大部分似乎仅能满足基本排课需求，如：

每班的课程不冲突：同一时间仅上一节课
每老师的课程不冲突：同一时间老师仅上一节课
某些时间区间需要上X节某课程
某些时间区间不上某课程

这对于一些课外培训学校可能已经足够了。

不过如果还有一些进阶的，特别是定制化排课需求，好像一般排课软件做不到，如：

老师上晚自习的次数尽量少，或同一老师一次晚上尽量多上几节晚自习。
同时为了公平，老师尽量上两天晚自习，即使可以一晚上完。
尽量避免同一老师同一天早自习和晚自习都有课，一天得不到休息
老师尽量有机会休息半天
某些时间尽量上某课程，但不强制（强制可能没有解）
学校有外教课，外教课仅在单周的周一周五上，每班外教课的双周对应于普通英语课，外教老师只有一个，不能同时上两班。
每周每科目教研时间不上课。

但排课软件的局限性也能理解：

因为这些进阶需求定制化比较高，进而不太方便简易格式化输入
- 致使要么软件的输入和设置非常复杂
- 要么需要专门编写代码来实现（即使代码本身不复杂，但也得占用一个开发人力）
定制化需求中特别是“尽量”这种关键词翻译到模型后，对应于最大化/最小化一些目标函数
- 比如“ 保证晚自习数量的情况下，让老师上晚上尽量可以少来学校” 这个目标。
- 比如“ 某些时间尽量上某课程，但不强制 ” 这个目标。
- 由于多个目标往往是相互冲突的，做不到全部最优。这时候需要定义一个综合指标来全面反应这些目标的达成度。
  - 要写出一个好的综合指标函数并不是非常简单的事情，特别当要求很多很杂时，可能需要多次求解和调参。
  - 更麻烦的是老师方通常也无法将心中完美的课表的指标函数准确表达出来。需要多次调整才能慢慢磨合。这对软件方而言则是很高的服务成本。

自己写代码就可以在满足基本排课需求的前提下，任意添加定制化需求。

2. 思路说明

注：ChatGPT确实是当代很好的学习帮手，以前个人折腾很多问题需要付出大量的时间查询。这次这个问题靠ChatGPT辅助下，工作和黑悟空之余几天基本就整明白了。

啰嗦完了，开始聊用 python 排课的思路。

可以对照着代码看，代码中有简单的备注：

2.1 理解排课

2.1.1 从运筹学角度看排课

排课可以视作一个运筹学问题，可以有明确的解决思路：

是先用数学定义清楚问题（建模），再用找办法求解问题

首先我们需要对问题进行建模：

定义需要求解的变量（目标变量）
定义约束（根据需要去掉不能接受的那些情况）
定义求解目标（在解满足约束的情况下，找尽量优甚至最优的解）
- “任意满足约束的解都可以” 也是一种目标

建模以后则可以对问题进行求解：

方式1：自己写算法求解，如深搜、宽搜、随机搜、遗传算法、启发式算法、配合分支定界法或其他剪枝方式。
- 搜索中根据约束去掉那些不满足约束的解
- 在能满足约束的解中，根据目标找最优的解
方式2：用现成的整数规划/混合规划求解器求解

2.1.2 线性说明

运筹学中解决类似问题时，线性和凸性是很重要的。

线性的好处：

纯线性的问题一定是凸的，可以高效剪枝（可以用各个超平面将整个解空间二分，每次定界可以剪一大片），且最后很容易确定解是最优解。

凹问题或非线性的问题：

分支可能非常多，每次剪枝只能在局部空间慢慢剔，对高维问题而言就非常棘手。

所以通常我们应尽量使我们的约束和目标都尽量线性。

有一些方法可以将非线性问题转化为线性，最常用且有趣的就是 bigM 方法：https://en.wikipedia.org/wiki/Big_M_method

不过 bigM 方法也有代价，也会使求解变慢，特别是 bigM 过大时。

2.1.3 建模库和求解器踩坑记录

写深搜很简单，但略复杂的问题下，基本搜不出好的排课方案。

加入复杂算法写好点的求解器太麻烦了，且求解效率往往还是很低（不过其中的算法原理还是蛮有意思，可以学习）。

面向解决问题而言，能用现成的还是优先用现成的。

这几天尝试了以下的建模库和求解器，分别聊聊粗浅体验后的感受：

库	说明和个人体验
OR-Tools 建模库	OR-Tools 是谷歌开发的开源的建模和求解器。建模能力个人感觉蛮强大的，能直接支持一些非线性建模方式，如乘积约束、条件约束、绝对值约束、逻辑与约束等等。 OR-Tools 建模后仅能用 OR-Tools 求解。
Pyomo 建模库	Pyomo 是仅针对建模的，功能很强大，写出来的建模代码个人感觉最简洁清晰（定义多维目标变量时就能体现）。可以调用各种求解器，如 SCIP、Gurobi 等等。但不能调用 OR-Tools。
SCIP 建模库	个人感受 SCIP 建模能力上最弱。虽然弱也有弱的好处，类似用C语言的感受：让大家关注问题的底层，且能逼大家学会用 bigM 之类的有趣骚操作将非线性约束转化成线性约束。
OR-Tools 求解器	注意：OR-Tools 的 CpSolver 目前不支持 python3.12，求解会崩。坑了我好一会。否则当时我也不会去尝试其他求解器。但OR-Tools个人感受求解能力比较强，特别是并行性比较高，能把我的CPU跑满。
Gurobi 求解器	商业求解器，应该非常强大。但免费的个人版有问题规模的限制，大概仅支持1万个变量。我给年级排课的模型大概需要3万个变量，提示我不能用。但付费版又太贵了，暂感觉没必要。
SCIP 求解器	开源免费，能解 Pyomo 建的模。但个人尝试后，至少对排课问题而言，其效率有些低下，多数时候仅能利用10% CPU，并行性比较差。

个人踩坑流水账

先 OR-Tools 在个人的云服务器 jupyterlab 上跑，用python3.7，但云服务器性能有限，求一个满足约束的解都需要1分钟。
在家里 PC 搭 jupyterlab ，conda 默认 python3.12，3.12 的 jupyterlab 的自动排版插件蛮好用的。但跑 OR-Tools 会崩。
换用 SCIP 重新建模和求解。遇到一个奇怪的问题（后发现是我写的代码问题），猜测又是 python3.12 问题。
换用 Pyomo 建模，考虑这样更灵活，总不至于 python3.12 下所有库都有问题。并先尝试搭配 SCIP 求解。
换用 Pyomo 建模，奇怪的问题还是存在。但继续研究后找到并解决了。
发现模型复杂一些后 SCIP 求解太慢。
换用 Gurobi 求解器。用 Pyomo 建模确实方便，换求解器仅需要动很少量代码，建模和输出代码都不用动。
结果 Gurobi 免费版变量太少。
重新搭基于 python3.11 的 jupyterlab。重新换用 OR-Tools 进行建模和求解。并最终解决问题。

整体有些折腾，分享出来，大家可能能少踩一些坑。

3 代码实现

3.1 完整代码

Python实现年级排课和优化-代码

3.2 数据设置

设置好各种排课的基本信息，用于后续模型建立，如

班级数量
各老师负责的科目和班级
各个班级各个时间段需要的各个课程数量
- 如文科班的每周正课时间段共需要8节英语课
各科目教研的时间段（此阶段老师不上课）
等等

如各教师负责的科目，与此科目对应的班级

# 教师信息：名字：负责的科目和科目对应的班级
teachers_duties = {
    "teacher_28": {"语文": [1, 3]},
    "teacher_59": {"数学": [1, 7]},
    "teacher_18": {"英语": [1, 9]},
    "teacher_15": {"政治": [1, 3]},
    "teacher_6": {"历史": [1, 4, 6]},
    "teacher_46": {"地理": [1, 2, 6], "班会": [1]},
    "teacher_50": {"美术": [1, 2, 8, 9, 10]},
....

注：教师名字我全替换为了“teacher_X”，实际处理时，直接用真名就行

3.3 预处理

这个部分的代码主要是基于前面设置的数据，生成一些新的数据结构，方便后续使用。但并不提供新数据或信息。

3.4 设置模型

# 导入 ortools 的建模库
from ortools.sat.python import cp_model

# 创建模型
model = cp_model.CpModel()

# 创建目标变量：每班每节课的科目

# 注释掉的这部分是 pyomo 的建模方式，可见非常清晰直观
# model.course_vars = Var(
#     all_class_indexes,
#     all_days_indexes,
#     all_course_indexes,
#     all_subjects,
#     domain=Binary,
# )

# ortools 的变量申明方式就会丑不少，阅读性略差
course_vars = {}
for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in all_course_indexes:
            for the_subject in all_subjects:
                course_vars[the_class,the_day,the_index,the_subject] = model.NewBoolVar(f'course_vars{the_class}_{the_day}_{the_index}_{the_subject}')
                
# 创建目标变量：每班每节课是否是外教课
# model.is_spoken_course = Var(
#     model.all_class_indexes,
#     model.all_days_indexes,
#     model.all_course_indexes,
#     domain=Binary,
# )
is_spoken_course = {}
for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in all_course_indexes:
            is_spoken_course[the_class,the_day,the_index] = model.NewBoolVar(f'is_spoken_course{the_class}_{the_day}_{the_index}')

首先我们定义一批目标变量去包含想要求解问题的解空间：

对常规课（不含外教、教研）而言，定义一批变量指代：特定班、特定天、特定时候、是否上科目课

变量是布尔型，0值代表此班、此天、此时候、不上此科目课。1则上此科目课。
变量一共有班级数量*天数*每天时候数*科目数
对应于代码中的这个变量数组 course_vars[the_class,the_day,the_index,the_subject]

但由于我的排课需求中还需要考虑外教课：

外教课仅在单周的周一周五上，每班外教课的双周对应于普通英语课，外教老师只有一个，不能同时上两班。

外教课和其他常规课逻辑不太一致，前面定义的空间不足以包含外教课的所有可能性。

要么再给变量增加一个维度：单双周。但这样会使目标变量翻倍
或者新加一批变量来指代外教课信息：特定班、特定天、特定时候、是否上外教课

个人选择第二种方式

3.5 设置辅助变量

辅助变量可以方便后续建模约束时使用。

如我们要求：

对每个班级而言，早上正课的所有相同课需要连续上。
- 不能出现第一节和第三节上语文，第二节英语。

个人想到的建模方式是对每个班统计早上正课各个科目的总数和科目连堂次数（此节课和下节课一致）。要求对每个科目而言总数-1=连堂次数。

但为此需要统计各班早上正课各个科目的总数和各班早上正课区间各科目连堂次数

这些就是辅助变量。

从数学的角度上看，是一个约束在目标空间不太好做约束，就以合适的规则升到某更高维度，在更高维度的空间做线性约束。但最后还是仅用原空间的解。

# 创建变量指针哪些课程将连续上(对班级而言)
will_consecutive_by_class_time_subject = {}
for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in indexes_could_consecutive:
            for the_subject in all_subjects:
                will_consecutive_by_class_time_subject[the_class,the_day,the_index,the_subject] = model.NewBoolVar(f'will_consecutive_by_class_time_subject_{the_class}_{the_day}_{the_index}_{the_subject}')

# 创建约束使这些变量值能表征是否连堂
for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in indexes_could_consecutive:
            for the_subject in all_subjects:
                logic_cons_and(
                    model,
                    will_consecutive_by_class_time_subject[
                        the_class, the_day, the_index, the_subject
                    ],
                    [
                        course_vars[the_class, the_day, the_index, the_subject],
                        course_vars[
                            the_class, the_day, the_index + 1, the_subject
                        ],
                    ],
                )

还有其他辅助变量服务于其他约束或目标，略过

3.6 加各种约束

用 OR-Tools 对模型加约束

通用格式：model.Add(约束表达式)

如比较简单的约束：要求每个班同时仅上一节课

# 要求每个班同时仅上一节课
for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in all_course_indexes:
            model.Add(
                sum(
                    course_vars[the_class, the_day, the_index, the_subject]
                    for the_subject in all_subjects
                )
                == 1
            )

如各班各科每周的晚自习前后均匀，差值绝对值不能大于1。（主要原因是学校前两节晚自习可以讲题，后两节不行，为了平衡）

我的约束方式

half_evening = {"early": [10, 11], "late": [12, 13]}

# 用于统计各班各科每周前后晚自习的数量
half_evening_num_by_class_half_subject = {}
for half_name in half_evening.keys():
    for the_class in all_class_indexes:
        for the_subject in all_subjects:
            half_evening_num_by_class_half_subject[half_name,the_class,the_subject] = model.NewIntVar(0, max_section_len* len(all_days_indexes), f'half_evening_num_by_class_half_subject{half_name}_{the_class}_{the_subject}')

for the_class in all_class_indexes:
    for the_subject in filter(lambda x: x != "", all_subjects):
        for the_half_name, the_half_indexes in half_evening.items():
            model.Add(
                # 加约束统计各班各科每周前后晚自习的数量
                half_evening_num_by_class_half_subject[
                    the_half_name, the_class, the_subject
                ]
                == sum(
                    course_vars[the_class, the_day, the_index, the_subject]
                    for the_day in all_days_indexes
                    for the_index in the_half_indexes
                )
            )
        # 加约束要求各科前后差值小于1
        model.Add(
            half_evening_num_by_class_half_subject[
                "early", the_class, the_subject
            ]
            - half_evening_num_by_class_half_subject[
                "late", the_class, the_subject
            ]
            <= 1
        )
        # 加约束要求各科前后差值小于1
        model.Add(
            half_evening_num_by_class_half_subject["late", the_class, the_subject]
            - half_evening_num_by_class_half_subject[
                "early", the_class, the_subject
            ]
            <= 1
        )

3.7 加目标

3.7.1 定义目标变量

目标就是定义出变量，并靠约束使变量的值符合想要的值。

如希望教师需要出现的section总数（早自习、上午、下午、晚自习）尽量少。

则需要统计教师出现的section总数。

则可以定义变量 total_teacher_shows_day_section 并加约束使其等于section总数：

# 加中间辅助变量
teacher_num_by_day_section = {}
for the_day in all_days_indexes:
    for the_section in all_section:
        teacher_num_by_day_section[the_day, the_section] = model.NewIntVar(0, len(all_teachers), f'teacher_num_by_day_section_{the_day}_{the_section}')

for the_day in all_days_indexes:
    for the_section in all_section:
        model.Add(
            teacher_num_by_day_section[the_day, the_section]
            == sum(
                any_by_teacher_day_section[the_teacher, the_day, the_section]
                for the_teacher in all_teachers
            )
        )

# 加目标变量和约束
total_teacher_shows_day_section = model.NewIntVar(
    0, len(all_teachers) * len(all_days_indexes) * len(all_section),f"total_teacher_shows_day_section"
)
model.Add(
    total_teacher_shows_day_section
    == sum(
        teacher_num_by_day_section[the_day, the_section]
        for the_day in all_days_indexes
        for the_section in all_section
    )
)

3.7.1 定义目标函数

当我们定义好各种目标相关变量后，需要用一个函数把这些变量综合起来，并告诉模型需要最小化/最大化此函数

所以比如我用的是最小化，且内部是线性关系，则目标翻译出来是

系数是正的项尽量小
系数负的项尽量大
系数绝对值越大的项，越优先保证优化

model.Minimize(
    teacher_num_by_day_section[1, "evening"] * 100 # 教师尽量少上晚自习，或一次多上几节
    + teacher_num_by_day_section[2, "evening"] * 100
    + teacher_num_by_day_section[3, "evening"] * 100
    + teacher_num_by_day_section[4, "evening"] * 100
    + teacher_num_by_day_section[5, "evening"] * 100
    + teacher_num_by_day_section[7, "evening"] * 1000 # 周天的晚自习要特别对待，最高优先级，能少来就少来
    + total_teacher_shows_day_section * 10 # 需要上班的section尽量少
    - teacher_times_by_section_from_to["dawn","morning"] * 5 # 只上上午的班是好事
    - teacher_times_by_section_from_to["afternoon","evening"] *5 # 只上下午和晚上的班是好事
    + teacher_times_by_section_from_to["dawn","afternoon"] * 5 
    + teacher_times_by_section_from_to["morning","afternoon"] * 5
    + teacher_times_by_section_from_to["morning","evening"] * 20 # 尽量控制早上到晚自习都有课的情况
    + teacher_times_by_section_from_to["dawn","evening"] * 200 # 尽量不要某天从早自习上到晚自习
)

3.8 求解

3.8.1 设置hint（非必要）

由于每次从一无所知开始求解会比较慢，如果有个不错的解作为提示，求解理应更快。

不过实际体验下来，似乎作用并不大，哈哈哈

个人实现方式是求解后把 course_save_var 输出成 json 文件保存，求解前读取

import json
load_course_var = {}
with open('course_save_var_31499.json', 'r') as f:
    load_course_var = json.load(f)

for the_class in all_class_indexes:
    for the_day in all_days_indexes:
        for the_index in all_course_indexes:
            for the_subject in all_subjects:
                str_key = str((the_class,the_day,the_index,the_subject))
                model.AddHint(course_vars[the_class,the_day,the_index,the_subject],load_course_var[str_key])

3.8.2 使用OR-TOOLS求解

class SolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self):
        cp_model.CpSolverSolutionCallback.__init__(self)
        print(f"Start to find Solution")
        self.__solution_count = 0

    def OnSolutionCallback(self):
        # This method is called each time the solver finds a solution.
        print(f"Solution {self.__solution_count} : Objective Value = {self.ObjectiveValue()} Time = {self.WallTime()} s")
        # Access variables using the Value method, e.g., `self.Value(var_name)`
        self.__solution_count += 1

solution_printer = SolutionPrinter()
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 18000
status = solver.Solve(model,solution_printer)

solution_printer 是个预设的回调函数，帮助监控求解进度

max_time_in_seconds 是求解时间限制

找到最优解/达到时间限制/发现无解才会结束求解
可以随意修改这个值

3.9 输出到 xlsx

基本思路是先建好一个课表模板 excel 文件。

输出时根据模板的格式创建 excel 文件，然后往各个课程格子里面填值，完成课表输出。

4. 运行

由于加了回调函数，可以在运行中监控状态：当找到一个满足约束的更优解时会提示并输出当前的最好目标函数值和时间花费

输出 excel 前也可以草览某个班级的排课情况。（其他需要看的内容类似方式加代码即可）

5. 后记

运筹学这套建模和求解的这套方法，可以用在很多问题上，包括旅游路线规划，工程排期等等。

也是因为应用广泛且有价值才会有 Gurobi 这种贵兮兮的商业求解器。

运筹学思维可以帮助我们把问题有逻辑地清晰描述，并且描述复合目标时更明确、有优先级取舍（体现为目标函数形式、权重、等等）。

学习一下还是蛮有意思的。

大家有相关技术问题可以联系我，一起研究学习共同进步。

有排课需求的老师也可以和我联系，力所能及的话，我可以免费帮下忙，不过由于本人有工作和其他重要事情，帮忙的优先级和响应速度有限，望理解。

微信：pangrt

Python 实现年级排课和优化-说明

0. 简述

0.1 生成的课表

0.2 实现的功能

0.2 代码

0.3 Github工程和相关文件

1 出发点

2. 思路说明

2.1 理解排课

2.1.1 从运筹学角度看排课

2.1.2 线性说明

2.1.3 建模库和求解器踩坑记录

3 代码实现

3.1 完整代码

3.2 数据设置

3.3 预处理

3.4 设置模型

3.5 设置辅助变量

3.6 加各种约束

3.7 加目标

3.7.1 定义目标变量

3.7.1 定义目标函数

3.8 求解

3.8.1 设置hint（非必要）

3.8.2 使用OR-TOOLS求解

3.9 输出到 xlsx

4. 运行

5. 后记

发表评论取消回复

0. 简述

0.1 生成的课表

0.2 实现的功能

0.2 代码

0.3 Github工程和相关文件

1 出发点

2. 思路说明

2.1 理解排课

2.1.1 从运筹学角度看排课

2.1.2 线性说明

2.1.3 建模库和求解器踩坑记录

3 代码实现

3.1 完整代码

3.2 数据设置

3.3 预处理

3.4 设置模型

3.5 设置辅助变量

3.6 加各种约束

3.7 加目标

3.7.1 定义目标变量

3.7.1 定义目标函数

3.8 求解

3.8.1 设置hint（非必要）

3.8.2 使用OR-TOOLS求解

3.9 输出到 xlsx

4. 运行

5. 后记

相关文章

发表评论 取消回复

发表评论取消回复