创建学校课程表的算法

我正在开发一款广泛使用的调度引擎，可以做到这一点。是的，它是NP完全问题；最好的方法是近似找出最优解。当然，有很多不同的方法来确定哪一个是“最佳”解——例如，你更关心老师是否对他们的课程表感到满意，还是学生是否能选上所有的课程？
绝对最重要的问题是你需要尽早解决的是什么使得一种调度方式比另一种更好？也就是说，如果我有一个安排，Jones夫人在8点教数学，而Smith先生在9点教数学，那么与Jones夫人和Jones先生都在10点教数学相比，哪个更好？与Jones夫人在8点教数学而Jones先生在2点教数学相比，哪个更好？为什么？
我提供的主要建议是尽可能地将问题分解——也许是按课程、按教师、按房间——并首先解决子问题。然后，你应该会得到多个解决方案可供选择，需要选择一个最可能最优的。接下来，要考虑到后续子问题的需求，在评估其潜在解决方案时，要让“早期”子问题考虑到后期子问题的需求。然后，也许要考虑如何在陷入“没有有效解决方案”的状态时使自己脱离困境（假设你无法预见这些情况）。
通常情况下，我们处理的是高度资源受限的学校调度系统。学校不会有很多空着的房间或老师在休息室闲着白过一天。在解决方案丰富的环境中效果最好的方法并不一定适用于学校调度。同时，通常使用局部搜索优化算法对最终答案进行“打磨”，以获得更好的结果。

通常，约束编程是解决这类调度问题的好方法。在stackoverflow和Google上搜索“约束编程”和“调度”或“基于约束的调度”将产生一些好的参考资料。使用传统的优化方法如线性或整数优化时，思考这个问题可能有些困难，但这并非不可能。其中一个输出结果是：是否存在一个满足所有要求的时间表？这本身就是很有帮助的。

祝好运！

我曾为课程排课和考试排课设计商用算法。在前者中，我采用了整数规划算法；在后者中，我使用了启发式算法，该算法基于通过选择时间段交换来最大化目标函数的方式，与原始手动过程非常相似。实现这样的解决方案所需的关键是能够表示所有实际约束条件，并且需要确保人类排课员无法找到改进解决方案的方法。总体而言，算法部分相对简单易实现，主要难点在于准备数据库、用户界面以及报告统计数据（如房间利用率、用户教育等）等方面。

您可以使用遗传算法来解决这个问题，但最好不要：）。它可能太慢，参数调整可能太耗时等等。
还有其他成功的方法。所有这些方法都是在开源项目中实现的：

• 基于约束条件的方法
  • 在UniTime中实现（不是真正针对学校的）
  • 您还可以进一步使用整数规划。 乌迪内大学和Bayreuth大学（我参与其中）使用商业软件（ILOG CPLEX）成功完成
  • 基于规则的启发式方法-请参见Drools planner
• 不同的启发式方法-FET和我的

在这里查看排课软件列表。

我认为您应该使用遗传算法，因为：

• 它最适合大问题实例。
• 它在不精确的答案（不是最终最佳）的代价下产生了降低的时间复杂度。
• 通过调整未满足约束和偏好的适应度惩罚，可以轻松指定约束和偏好。
• 您可以为程序执行指定时间限制。

• 解决程序所需的时间越长，解决方案的质量就越高。

  遗传算法定义

  遗传算法教程

  GA课程安排项目

还要看看：一个类似的问题和另一个问题

这个问题在我的工作中非常严重——想象一下有1800个科目/模块和350,000名学生，每个学生要做5到10个模块，在10周内编写1小时到3天的试卷……一个加分点是所有考试都在线上进行，但是又不好的是不能超过系统最大5k并发的负载。所以现在我们正在使用云端扩展服务器来解决这个问题。 我们使用的“解决方案”只是简单地按照与其他模块“冲突”的数量降序排列（即一个学生同时参加两个模块），然后“背包”它们，允许这些长论文实际上重叠，否则就无法完成了。 所以当事情变得太大时，我发现这个“启发式算法”是实用的……至少。

我不知道有多少人会同意这段代码，但是我用自己的算法编写了这段代码，在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
                                                @finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
                                                @finaltt.employee_id=@subjectdetail.employee_id
                                                @finaltt.section_id=section.id
                                                @finaltt.standard_id=standard.id
                                                @finaltt.division_id=division.id
                                                @finaltt.subject_id=@subjectdetail.subject_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

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

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

它允许:

1. 定义学习期
2. 定义每天的课程限制
3. 定义每个组每天重复相同课程的最大次数(比如任何组一天内不应该有4节数学课)
4. 每天每组的课程限制，所以不应该出现一个组一天上10节课的情况
5. 其他东西都很基本，你只需要定义一个组和他们的课程要求来填写学习期。