创建学校时间表的算法

Question

我一直想知道是否有已知的创建学校时间表的算法解决方案。基本上，它是关于优化给定班级-学科-教师协会的“时间分散”（在教师和班级情况下）。我们可以假设我们有一组在输入时相互关联的课程、课程科目和教师，并且时间表应适合上午 8 点到下午 4 点之间。

我想可能没有准确的算法，但也许有人知道一个很好的近似值或开发它的提示。

Answer 1

这个问题是NP完全问题！
简而言之，我们需要探索所有可能的组合，以找到可接受的解决方案列表。由于不同学校出现问题的情况有所不同（例如：教室是否有限制？、某些班级是否有时会分成小组？、这是每周的时间表吗？）等）不存在与所有调度问题相对应的众所周知的问题类别。也许，背包问题与这些问题有许多相似之处大的。

要确认这既是一个难题，又是人们不断寻求解决方案的问题，请检查此（长）（主要是商业）软件调度工具列表

由于涉及大量变量，其中最大的来源通常是教师成员的愿望;-)...，考虑枚举所有可能的组合通常是不切实际的。相反，我们需要选择一种访问问题/解决方案空间子集的方法。
- 另一个答案中引用的遗传算法（或者，恕我直言，似乎）能够很好地执行这种半引导搜索（问题是找到一个好的评估为下一代保留候选人的功能）
- 图重写方法也可用于此类组合优化问题。

我不想专注于自动计划生成器程序的特定实现，而是想建议一些可以在问题定义层面应用的策略 .
一般的理由是，在大多数现实世界的调度问题中，需要一些妥协，而不是所有明示和暗示的约束：都将得到完全满足。因此，我们通过以下方式帮助自己：

• 定义所有已知约束并对其进行排序
• 通过手动提供一组附加约束来减少问题空间。
  这可能看起来违反直觉，但例如通过提供初始值，部分填充的时间表（例如大约 30% 的时隙），以完全满足所有约束的方式，并且通过考虑此部分时间表不可变，我们显着减少了生成候选解决方案所需的时间/空间。
  另一个额外约束的帮助方式是例如“人为”添加一个约束，阻止在一周的某些日子教授某些科目（如果这是每周的时间表......）；这种类型的约束会导致问题/解决方案空间的减少，并且通常不会排除大量好的候选者。
• 确保可以快速计算问题的一些约束。这通常与用于表示问题的数据模型的选择相关；这个想法是能够快速选择（或删除）一些选项。
• 重新定义问题并允许打破一些约束几次（通常是朝向图的末端节点）。这里的想法是要么删除一些填充时间表中最后几个空位的约束，要么让自动时间表生成器程序停止羞于完成整个时间表，而是为我们提供一个十几个可能的候选人名单。正如所指出的，人类通常能够更好地完成拼图，可能会使用通常不与自动化逻辑共享的信息来打破一些约束（例如，“下午没有数学”规则有时会被打破）对于“高级数学和物理”课程；或“打破琼斯先生的一项要求比史密斯女士的一项要求更好......;-)）

在校对这个答案时，我意识到它很羞于提供一个明确的答复，但仍然充满了实际的建议，我希望这对解决“难题”有所帮助。

Answer 2

真是一团糟。皇家混乱。为了补充已经非常完整的答案，我想指出我的家庭经历。我的母亲是一名教师，曾经参与过这个过程。

事实证明，让计算机这样做不仅本身很难编码，而且还很困难，因为有些条件很难指定给预先烘焙的计算机程序。示例：

• 一位老师既在您的学校又在另一所学院任教。显然，如果他在 10.30 在那里结束课程，他就无法在 10.30 开始在您的场所上课，因为他需要一些时间在各个学院之间通勤。
• 两位老师已婚。一般来说，同一班级最好不要有两名已婚教师。因此，这两位老师必须有两个不同的班级，
• 两位老师已结婚，并且他们的孩子在同一所学校上学。同样，你必须阻止这两位老师在他们的孩子所在的特定班级授课。
• 学校有独立的设施，比如有一天班级在一个学院，另一天班级在另一所。
• 学校有共用实验室，但这些实验室仅在某些工作日开放（出于安全原因，例如需要额外人员时）。
• 有些老师喜欢自由日：有些喜欢周一，有些喜欢周五，有些喜欢周三。有些人喜欢早上早点来，有些人则喜欢晚点来。
• 你不应该出现这样的情况：第一个小时是历史课，然后是三个小时的数学课，然后又是一个小时的历史课。这对于学生来说没有意义，对于老师来说也没有意义。
• 你应该均匀地传播论点。一周的头几天只学数学，然后剩下的时间只学文学，这是没有意义的。
• 你应该给一些老师连续两个小时的时间来进行评估测试。

正如你所看到的，这个问题不是 NP 完全问题，而是 NP 疯狂问题。

所以他们所做的就是有一张大桌子，上面有小塑料镶嵌物，然后移动这些镶嵌物，直到获得满意的结果。他们从不从头开始：他们通常从上一年的时间表开始并进行调整。

Answer 3

2007 年国际时间表竞赛有一个课程安排轨道和考试安排轨道。许多研究人员参加了那次比赛。人们尝试了很多启发式算法和元启发式算法，但最终局部搜索元启发式算法（例如禁忌搜索和模拟退火）明显击败了其他算法（例如遗传算法）。

看看一些决赛入围者使用的 2 个开源框架：

• JBoss OptaPlanner（Java，开源）
• < a href="http://www.unitime.org/" rel="noreferrer">Unitime（Java，开源） - 更多适合大学

Answer 4

我的期中作业之一是遗传算法学校表格生成。

整张桌子就是一个“有机体”。通用遗传算法方法有一些变化和警告：

• 针对“非法表格”制定了规则：同一教室里有两个班级，一名教师同时教授两个小组等。这些突变被立即视为致命的，并且一个新的“有机体”立即在“死者”的位置上萌芽。最初的一个是通过一系列随机尝试生成的，以获得合法的（如果毫无意义的话）。致命突变不计入迭代突变计数。

• “交换”突变比“修改”突变更常见。变化只发生在基因中有意义的部分之间——不能用教室代替老师。

• 将某些 2 小时捆绑在一起、为同一组按顺序分配相同的通用教室、保持教师的工作时间和班级负荷连续，会获得小额奖金。如果为特定科目提供正确的教室、将上课时间控制在一定范围内（上午或下午）等，则会获得适度的奖金。大奖金是分配给定科目的正确数量、给定教师的工作量等。

• 教师可以创建“然后想工作”，“然后可以工作”，“然后不喜欢工作”的工作量计划”、“那么无法工作”，并分配了适当的权重。整个 24 小时都是合法的工作时间，除了晚上的时间是非常不受欢迎的。

• 权重函数...哦是的。权重函数是分配给选定特征和属性的权重的巨大且巨大的乘积（如乘法）。它非常陡峭，一种属性很容易就能将其向上或向下改变一个数量级——而且一个有机体中有数百或数千种属性。这导致权重的数字绝对巨大，并且直接结果是需要使用 bignum 库 (gmp) 来执行计算。对于大约 10 个小组、10 名教师和 10 个教室的小型测试用例，初始集以 10^-200something 的音符开始，以 10^+300something 的音符结束。当它更平坦时，它的效率完全低下。此外，随着“学校”规模的扩大，这些值的距离也会变得更宽。

• 就计算时间而言，长时间的小群体（100）和少代的大群体（10k+）之间几乎没有区别。相同时间的计算产生了大致相同的质量。

• 对于上述 10x10x10 测试用例，计算（在某些 1GHz CPU 上）需要大约 1 小时才能稳定在 10^+300 附近，生成看起来相当不错的时间表。

• 通过提供在运行计算的计算机之间交换最佳样本的网络设施，该问题可以轻松并行化。

  通过提供在运行计算的计算机之间交换最佳样本的网络设施，该问题

最终的项目从未让我在这个学期取得好成绩。它显示出了一些希望，但我从未有足够的动力来添加任何 GUI 并使其可供公众使用。

Answer 5

我的时间表算法，在 FET 中实现（免费时间表软件，http://lalescu.ro/liviu/fet/ ，成功的应用）：

该算法是启发式的。我将其命名为“递归交换”。

输入：一组活动 A_1...A_n 和约束。

输出：一组时间 TA_1...TA_n（每个活动的时间段。为简单起见，此处不包括房间）。该算法必须将每个活动放在一个时间段，并遵守约束。每个TA_i在0(T_1)和max_time_slots-1(T_m)之间。

约束：

C1) 基本：一系列不能同时进行的活动（例如，A_1 和 A_2，因为它们有相同的老师或相同的学生）；

C2) 许多其他约束（为简单起见，此处排除）。

时间表算法（我将其命名为“递归交换”）：

1. 对活动进行排序，最困难的排在前面。不是关键步骤，但可以将算法速度加快 10 倍或更多。

2. 尝试将每个活动 (A_i) 放置在允许的时间段中，按照上述顺序，一次一个。搜索 A_i 的可用槽 (T_j)，可以在其中放置此活动并遵守约束。如果有更多可用插槽，请随机选择一个。如果没有可用的，则进行递归交换：

   一个。对于每个时隙 T_j，考虑如果将 A_i 放入 T_j 中会发生什么。将会有一系列与此移动不相符的其他活动（例如，活动 A_k 位于同一槽 T_j 上，并且与 A_i 具有相同的老师或相同的学生）。保留每个时间段 T_j 的冲突活动列表。

   b。选择冲突活动数量最少的槽 (T_j)。假设此槽中的活动列表包含 3 个活动：A_p、A_q、A_r。

   c。将 A_i 放置在 T_j 处，并使 A_p、A_q、A_r 未分配。

   d。递归地尝试将A_p、A_q、A_r（如果递归级别不是太大，比如14，并且如果从步骤2开始计算的递归调用总数）放在A_i开始的位置不是太大，比如2*n），如步骤 2) 所示。

   e。如果成功放置A_p、A_q、A_r，则成功返回，否则尝试其他时间段（转到步骤2 b）并选择下一个最佳时间段）。

   f。如果所有（或合理数量的）时间段均尝试失败，则返回但不成功。

   g。如果我们处于级别 0，并且我们没有成功放置 A_i，则像步骤 2 b) 和 2 c) 那样放置它，但不使用递归。我们现在还有 3 - 1 = 2 项活动要开展。转到步骤 2)（这里使用了一些避免循环的方法）。

Answer 6

这个问题比看起来更难。

正如其他人提到的，这是一个 NP 完全问题，但让我们分析一下这意味着什么。

基本上，这意味着您必须考虑所有可能的组合。

但“看看”并不能告诉你需要做什么。

生成所有可能的组合很容易。它可能会产生大量数据，但是理解这部分问题的概念应该不会有太大问题。

第二个问题是判断给定的可能组合是好、坏还是比先前的“好”解决方案更好。

为此，您需要的不仅仅是“这是否是一个可能的解决方案”。

例如，同一位老师是否连续 X 周每周工作 5 天？即使这是一个可行的解决方案，也可能不是比两个人轮流让每个老师各做一周更好的解决方案。哦，你没想过吗？请记住，这是你要面对的人，而不仅仅是资源分配问题。

即使一名教师可以连续全职工作 16 周，与尝试在教师之间轮流的解决方案相比，这可能不是一个次优的解决方案，而且这种平衡很难构建到软件中。

总而言之，对于很多人来说，为这个问题找到一个好的解决方案是非常有价值的。因此，这不是一个容易分解和解决的问题。准备好制定一些不是 100% 的目标，并称它们“足够好”。

Answer 7

更新：从评论中......也应该有启发式！

我会选择 Prolog ...然后使用 Ruby 或 Perl 或其他东西将您的解决方案清理成更漂亮的形式。

teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

我（仍然）正在做与这个问题类似的事情，但使用与我刚才提到的相同的路径。 Prolog（作为一种函数式语言）确实使解决 NP-Hard 问题变得更加容易。

Answer 8

遗传算法通常用于此类调度。

发现这个例子（使用遗传算法制作课程表）非常符合您的要求。

Answer 9

以下是我找到的一些链接：

学校时间表 - 列出了涉及的一些问题

学校时间表的混合遗传算法

日程安排实用程序和工具

Answer 10

本文很好地描述了学校时间表问题及其算法方法：“SYLLABUS 的开发——面向学校和学院的交互式、基于约束的调度程序。"[PDF]

作者告诉我 SYLLABUS 软件仍在使用/开发中：http://www.scientia.com/uk/

Answer 11

我正在研究一个广泛使用的调度引擎，它正是这样做的。是的，它是 NP 完全的；最好的方法寻求近似最佳解决方案。当然，有很多不同的方法可以说哪一种是“最佳”解决方案 - 例如，您的老师对他们的日程安排感到满意，还是学生进入所有课程更重要？

您需要尽早解决的绝对最重要的问题是是什么让一种调度该系统的方法比另一种更好？也就是说，如果我有一个时间表，琼斯夫人在 8 点教数学，史密斯先生在 9 点教数学，那么这比他们两人在 10 点教数学的时间表更好还是更差？这比琼斯夫人在 8 点教课、琼斯先生在 2 点教课更好还是更差？为什么？

我在这里给出的主要建议是尽可能地划分问题——也许是一个课程一个课程，也许一个一个老师，一个一个房间——然后首先解决子问题。在那里，您最终应该有多种解决方案可供选择，并且需要选择一个作为最可能的最佳解决方案。然后，努力使“早期”子问题在对其潜在解决方案进行评分时考虑到后期子问题的需求。然后，当您进入“无有效解决方案”状态时，也许可以研究如何使自己摆脱陷入困境的情况（假设您无法在早期子问题中预见到这些情况）。

本地搜索优化过程通常用于“打磨”最终答案以获得更好的结果。

请注意，我们通常在学校调度中处理资源高度受限的系统。学校全年不会有很多空房间，或者老师一天 75% 的时间都坐在休息室里。在解决方案丰富的环境中最有效的方法不一定适用于学校安排。

Answer 12

一般来说，约束规划是解决此类调度问题的好方法。在 Stack Overflow 和 Google 上搜索“约束编程”和调度或“基于约束的调度”将产生一些很好的参考。这并非不可能——只是在使用线性或整数优化等传统优化方法时有点难以思考。一个输出是 - 是否存在满足所有要求的时间表？这本身显然是有帮助的。

祝你好运 ！

Answer 13

我为课程时间表和考试时间表设计了商业算法。第一次我使用整数规划；对于第二个，基于通过选择槽交换来最大化目标函数的启发式，与已经发展的原始手动过程非常相似。让此类解决方案被接受的主要因素是能够代表所有现实世界的约束；并且人类时间表人员无法找到改进解决方案的方法。最后，与数据库的准备、用户界面、报告房间利用率、用户教育等统计数据的能力相比，算法部分非常简单且易于实现。

Answer 14

是的，你可以用遗传算法来解决它。但你不应该:)。它可能太慢，参数调整可能太耗时等等。

还有其他成功的方法。全部在开源项目中实现：

• 基于约束的方法
  • 在 UniTime 中实现（并非真正针对学校）
  • 您还可以进一步使用整数编程。在乌迪内大学和拜罗伊特大学成功完成（我参与其中）使用商业软件（ILOG CPLEX）
  • 基于规则的启发式方法 - 请参阅 Drools planner
• 不同的启发式 - FET 和 我自己的

请参阅此处时间表软件列表

Answer 15

在我工作的地方，这个问题非常严重 - 想象一下，有 1800 个科目/模块，350 000 名学生，每个学生做 5 到 10 个模块，并且您希望在 10 周内完成一次考试，其中试卷长度为 1 小时到 3 天……加分点-所有考试都是在线的，但又不好，不能超过系统最大5k并发负载。所以，是的，我们现在正在云中的扩展服务器上执行此操作。
我们使用的“解决方案”只是根据模块与降序“冲突”的其他模块数量进行排序（学生两者都做），并“打包”它们，允许这些长论文实际上重叠，否则它根本无法完成吧。
因此，当事情变得太大时，我发现这种“启发式”是实用的……至少是这样。

Answer 16

我不知道有人会同意这段代码，但我在自己的算法的帮助下开发了这段代码，并在 ruby​​ 中为我工作。希望它能帮助那些正在寻找它的人
在下面的代码中，periodflag，dayflag subjectflag和teacherflag是具有相应id和布尔值的标志值的散列。
有任何问题请联系我......(-_-)

periodflag.each do |k2,v2|

            if(TimetableDefinition.find(k2).period.to_i != 0)
                subjectflag.each do |k3,v3|
                    if (v3 == 0)
                        if(getflag_period(periodflag,k2))
                            @teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
                            @teacherlists=Employee.find(@teachers)
                            teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle] 
                            teacherflag.each do |k4,v4|
                                if(v4 == 0)
                                    if(getflag_subject(subjectflag,k3))
                                        subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
                                        if subjectperiod.blank?
                                            issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
                                            if issubjectpresent.blank?
                                                isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
                                                if isteacherpresent.blank?
                                                    @finaltt=TimetableAssign.new
                                                    @finaltt.timetable_struct_id=@timetable_struct.id
                                                    @finaltt.employee_id=k4
                                                    @finaltt.section_id=section.id
                                                    @finaltt.standard_id=standard.id
                                                    @finaltt.division_id=division.id
                                                    @finaltt.subject_id=k3
                                                    @finaltt.timetable_definition_id=k2
                                                    @finaltt.timetable_day_id=k1
                                                    set_school_id(@finaltt,current_user)
                                                    if(@finaltt.save)

                                                        setflag_sub(subjectflag,k3,1)
                                                        setflag_period(periodflag,k2,1)
                                                        setflag_teacher(teacherflag,k4,1)
                                                    end
                                                end
                                            else
                                                @subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
                                                @finaltt=TimetableAssign.new
                                                @[email protected]_struct_id
                                                @[email protected]_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @[email protected]_id
                                                @finaltt.timetable_definition_id=k2
                                                @finaltt.timetable_day_id=k1
                                                set_school_id(@finaltt,current_user)
                                                if(@finaltt.save)

                                                    setflag_sub(subjectflag,k3,1)
                                                    setflag_period(periodflag,k2,1)
                                                    setflag_teacher(teacherflag,k4,1)
                                                end
                                            end
                                        end
                                    end
                                end
                            end
                        end
                    end
                end
            end
        end

Answer 17

我尝试使用两阶段最大流并巧妙地构建图表来创建一个

您可以在这里看到它： https://github .com/Kemsekov/SchoolScheduleCreator

它允许

1. 定义学习周期
2. 定义每天的课程限制
3. 定义每组每天重复的最大相同课程（就像任何组每天不应该有 4 节数学课）
4. 每组的课程限制小组一天，所以不应该有一个小组每天有 10 节课的情况。
5. 其他的东西是非常基本的，你只需要定义一个小组和他们的课程的要求来填写一个学习周期。