我一直想知道创建学校时间表的算法是否有已知的解决方案。基本上，它是关于为给定的班级-科目-教师协会优化“小时分散”（在教师和班级情况下）。我们可以假设我们有一组在输入时相互关联的课程、课程科目和教师，并且时间表应该适合于上午 8 点到下午 4 点之间。
我想可能没有准确的算法，但也许有人知道一个很好的近似值或开发它的提示。
问问题
81107 次
17 回答
100
这个问题是NP完全的！
简而言之，需要探索所有可能的组合以找到可接受的解决方案列表。由于不同学校出现问题的情况有所不同（例如：教室是否有限制？是否某些班级有时会分成小组？这是每周安排吗？等等）没有一个众所周知的问题类别对应于所有的调度问题。也许，背包问题与这些问题有很多相似之处。
确认这既是一个难题，也是人们长期寻求解决方案的一个问题，就是检查这个（长）列表（主要是商业）软件调度工具
由于涉及大量变量，其中最大的来源通常是教员的愿望;-)...，考虑列举所有可能的组合通常是不切实际的。相反，我们需要选择一种访问问题/解决方案空间子集的方法。
-在另一个答案中引用的遗传算法（或者，恕我直言，似乎）装备精良，可以执行这种半引导搜索（问题是为下一代保留的候选者找到一个好的评估函数）
-图重写方法也可用于此类组合优化问题。
与其专注于自动调度生成程序的特定实现，我想提出一些可以在问题定义级别应用的策略。
一般的理由是，在大多数现实世界的调度问题中，将需要一些妥协，而不是所有明示和暗示的约束：都将得到完全满足。因此，我们通过以下方式帮助自己：
- 定义和排列所有已知的约束
- 通过手动减少问题空间，提供一组额外的约束。
这可能看起来违反直觉，但例如通过提供一个初始的、部分填充的时间表（比如大约 30% 的时隙），以完全满足所有约束的方式，并且通过考虑这个部分时间表是不可变的，我们显着减少了产生候选解决方案所需的时间/空间。
其他约束帮助的另一种方式是例如“人为”添加一个约束，以防止在一周中的某些日子教授某些科目（如果这是每周计划......）；这种类型的约束会导致减少问题/解决方案空间，而通常不会排除大量好的候选者。 - 确保可以快速计算问题的某些约束。这通常与用于表示问题的数据模型的选择有关；这个想法是能够快速选择（或删除）一些选项。
- 重新定义问题并允许一些约束被打破，几次，（通常朝向图的末端节点）。这里的想法是要么删除一些用于填写日程表中最后几个空位的限制，要么让自动日程表生成器程序停止完成整个日程表，而不是为我们提供一打左右看似合理的列表候选人。如前所述，人类通常处于更好的位置来完成难题，可能会打破一些限制，使用通常不会与自动逻辑共享的信息（例如，“下午没有数学”规则有时会被打破对于“高级数学和物理”课程；或“最好打破琼斯先生的一项要求，而不是史密斯女士的一项要求……;-))
在校对这个答案时，我意识到它很难提供明确的回应，但它仍然充满了实用的建议。我希望这对毕竟是一个“难题”有所帮助。
于 2010-02-01T17:11:51.903 回答
56
一团糟。皇室混乱。为了补充已经非常完整的答案，我想指出我的家庭经历。我的母亲是一名教师，曾经参与过这个过程。
事实证明，拥有一台计算机不仅难以编码本身，而且也很困难，因为有些条件难以指定给预烘焙的计算机程序。例子：
- 一位老师在您的学校和另一所学院任教。显然，如果他在 10.30 结束课程，他不能在 10.30 开始在您的场所，因为他需要一些时间在学院之间通勤。
- 两位老师结婚了。一般来说，最好不要在同一个班级有两位已婚教师。因此，这两位老师必须有两个不同的班级
- 两位老师结婚了，他们的孩子在同一所学校上学。同样，您必须阻止两位老师在他们孩子所在的特定班级任教。
- 学校有独立的设施，比如一天在一个学院上课，一天在另一个学院上课。
- 学校有共享实验室，但这些实验室仅在某些工作日开放（出于安全原因，例如需要额外人员的情况下）。
- 有些老师对自由日有偏好：有些喜欢周一，有些喜欢周五，有些喜欢周三。有些人喜欢一大早来，有些人喜欢晚点来。
- 你不应该有这样的情况，比如第一个小时上历史课，然后是三个小时的数学课，然后是另一个小时的历史课。这对学生没有意义，对老师也没有意义。
- 你应该均匀地传播论点。一周中的第一天只有数学，然后一周的其余时间只有文学是没有意义的。
- 你应该给一些老师连续两个小时做评估测试。
如您所见，问题不是 NP 完全的，而是 NP 疯狂的。
所以他们所做的是他们有一张带有小塑料嵌件的大桌子，他们四处移动嵌件，直到获得令人满意的结果。他们从不从头开始：他们通常从上一年的时间表开始并进行调整。
于 2010-02-01T17:33:31.507 回答
29
2007年国际时间表竞赛有一个课程安排轨道和考试安排轨道。许多研究人员参加了那场比赛。尝试了很多启发式算法和元启发式算法，但最终局部搜索元启发式算法（例如禁忌搜索和模拟退火）明显击败了其他算法（例如遗传算法）。
看看一些决赛选手使用的 2 个开源框架：
- JBoss OptaPlanner（Java，开源）
- Unitime (Java, 开源) - 更多的大学
于 2011-12-20T16:53:00.523 回答
18
我的一项半学期作业是遗传算法课桌生成。
整张桌子是一个“有机体”。通用遗传算法方法有一些变化和警告：
为“非法桌子”制定了规则：同一个教室两个班，一个老师同时教两个小组等等。这些突变被认为是立即致命的，一个新的“有机体”立即在“死者”的位置上萌芽。最初的一个是通过一系列随机尝试生成的，以获得一个合法的（如果毫无意义的话）一个。致命突变不计入迭代中的突变计数。
“交换”突变比“修改”突变更常见。变化只发生在有意义的基因部分之间——没有用教室代替老师。
将某些 2 小时捆绑在一起，为同一组按顺序分配相同的通用教室，以保持教师的工作时间和课堂负荷的连续性，分配了小额奖金。为给定主题提供正确的教室，将上课时间保持在债券（上午或下午）之内等，会分配适度的奖金。巨大的奖金是分配正确数量的给定科目，给老师的工作量等。
教师可以创建他们的工作量时间表，“然后想工作”、“那么可以工作”、“那时不喜欢工作”、“那么不能工作”，并分配适当的权重。整个 24 小时都是合法的工作时间，除了晚上是非常不受欢迎的。
权重函数...哦，是的。权重函数是分配给选定特征和属性的权重的巨大、可怕的乘积（如乘法）。它非常陡峭，一个属性很容易将它上下改变一个数量级——一个有机体有成百上千个属性。这导致绝对巨大的数字作为权重，并且作为直接结果，需要使用 bignum 库 (gmp) 来执行计算。对于大约 10 个小组、10 位教师和 10 个教室的小测试用例，初始集以 10^-200something 的音符开始，以 10^+300something 的音符结束。当它更平坦时，它完全没有效率。此外，随着“学校”的扩大，价值观的差距也越来越大。
在计算时间方面，长时间的小种群（100）和少世代的大种群（10k+）之间几乎没有区别。同一时间的计算产生了大致相同的质量。
计算（在一些 1GHz CPU 上）需要大约 1 小时才能稳定在 10^+300 附近，生成看起来相当不错的时间表，对于所说的 10x10x10 测试用例。
通过提供可以在运行计算的计算机之间交换最佳样本的网络设施，这个问题很容易并行化。
由此产生的程序从来没有看到外面的阳光让我在这个学期取得好成绩。它显示了一些希望，但我从来没有足够的动力来添加任何 GUI 并使其对公众可用。
于 2010-02-02T12:37:13.453 回答
9
这个问题比看起来更难。
正如其他人所暗示的那样，这是一个 NP 完全问题，但让我们分析一下这意味着什么。
基本上，这意味着您必须查看所有可能的组合。
但是“看”并不能告诉你太多你需要做什么。
生成所有可能的组合很容易。它可能会产生大量数据，但理解这部分问题的概念应该不会有太大问题。
第二个问题是判断一个给定的可能组合是好、坏还是比前面的“好”解决方案更好。
为此，您需要的不仅仅是“这是一个可能的解决方案”。
例如，同一位老师是否连续 X 周每周工作 5 天？即使这是一个可行的解决方案，它也可能不是比两个人交替进行更好的解决方案，这样每个老师每个星期做一个星期。哦，你没想到吗？请记住，这是与您打交道的人，而不仅仅是资源分配问题。
即使一位教师可以连续 16 周全职工作，与您尝试在教师之间交替的解决方案相比，这可能是一个次优的解决方案，而且这种平衡很难内置到软件中。
总而言之，对很多人来说，为这个问题提供一个好的解决方案将很有价值。因此，这不是一个容易分解和解决的问题。准备好标出一些不是 100% 的目标，并称它们“足够好”。
于 2010-02-05T22:10:21.717 回答
8
我的时间表算法，在 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) 许多其他约束（为简单起见，此处不包括在内）。
时间表算法（我将其命名为“递归交换”）：
- 对活动进行排序，最困难的在前。不是关键步骤，但可以将算法加速 10 倍或更多。
尝试按照上述顺序将每个活动 (A_i) 放置在允许的时间段内，一次一个。为 A_i 搜索一个可用的插槽 (T_j)，可以在其中放置此活动以尊重约束。如果有更多可用的插槽，请随机选择一个。如果没有可用，请执行递归交换：
一个。对于每个时隙 T_j，考虑如果将 A_i 放入 T_j 会发生什么。将有一个不同意此移动的其他活动的列表（例如，活动 A_k 与 A_i 在同一插槽 T_j 上，并且具有相同的老师或相同的学生）。为每个时隙 T_j 保留一个冲突活动列表。
乙。选择冲突活动数量最少的槽 (T_j)。假设此插槽中的活动列表包含 3 个活动：A_p、A_q、A_r。
丙。将 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，则返回成功，否则尝试其他时隙（转到步骤2b）并选择下一个最佳时隙）。
f . 如果所有（或合理数量的）时间段尝试失败，则返回失败。
克。如果我们处于第 0 级，并且我们没有成功放置 A_i，则像步骤 2 b) 和 2 c) 一样放置它，但不要递归。我们现在还有 3 - 1 = 2 个活动要安排。转至第 2 步）（此处使用了一些避免循环的方法）。
于 2011-06-04T08:47:42.160 回答
6
更新：来自评论......也应该有启发式！
我会使用 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 问题更容易。
于 2010-02-01T15:45:09.630 回答
5
遗传算法通常用于这种调度。
发现这个例子（使用遗传算法制定课程表）非常符合您的要求。
于 2010-02-01T15:45:52.280 回答
5
于 2010-02-01T15:50:05.737 回答
4
本文很好地描述了学校时间表问题及其对算法的处理方法：“教学大纲的开发——一种面向学校和学院的交互式、基于约束的调度程序。 ”[PDF]
作者在这里告诉我 SYLLABUS 软件仍在使用/开发：http ://www.scientia.com/uk/
于 2010-05-04T01:34:16.060 回答
3
我在一个广泛使用的调度引擎上工作，它正是这样做的。是的，它是 NP 完全的；最好的方法寻求近似最优解。而且，当然有很多不同的方式可以说哪一个是“最好的”解决方案——例如，让你的老师对他们的日程安排感到满意，还是让学生进入他们所有的课程更重要？
您需要尽早解决的绝对最重要的问题是，是什么让一种调度这个系统的方式比另一种更好？也就是说，如果我有一个时间表，琼斯夫人在 8 岁时教数学，而史密斯先生在 9 岁时教数学，那比他们俩都在 10 岁时教数学的时间表好还是差？琼斯夫人在 8 岁时教书，琼斯先生在 2 岁时教书，这比一个好还是坏？为什么？
我在这里给出的主要建议是尽可能地把问题分开——也许是逐个课程，也许是逐个老师，也许是逐个房间——然后首先解决子问题。在那里，您最终应该有多种解决方案可供选择，并且需要选择一个作为最可能的最佳解决方案。然后，在制作“早期”子问题的工作中，考虑到后期子问题在对其潜在解决方案进行评分时的需求。然后，当你进入“没有有效的解决方案”状态时，也许可以研究如何让自己摆脱困境（假设你无法在早期的子问题中预料到这些情况）。
本地搜索优化通行证通常用于“润色”最终答案以获得更好的结果。
请注意，通常我们在学校调度中处理高度资源受限的系统。学校一年中不会有很多空房间或一天 75% 的时间里都坐在休息室里的老师。在解决方案丰富的环境中效果最好的方法不一定适用于学校安排。
于 2014-03-27T18:59:42.757 回答
2
一般来说，约束规划是解决这类调度问题的好方法。在堆栈溢出和 Google 上搜索“约束编程”和调度或“基于约束的调度”将产生一些很好的参考。这并非不可能——只是在使用线性或整数优化等传统优化方法时有点难以思考。一个输出是 - 是否存在满足所有要求的时间表？这本身显然是有帮助的。
祝你好运 ！
于 2010-02-01T15:45:25.247 回答
2
我为课堂时间表和考试时间表设计了商业算法。首先，我使用整数编程；第二个启发式基于通过选择插槽交换来最大化目标函数，非常类似于已经进化的原始手动过程。让此类解决方案被接受的主要因素是能够表示所有现实世界的约束；并且人类时间表人员无法找到改进解决方案的方法。最后，与数据库的准备、用户界面、报告房间利用率、用户教育等统计数据的能力相比，算法部分非常简单易行。
于 2010-02-05T22:00:56.323 回答
2
你可以用遗传算法来解决它，是的。但你不应该:)。它可能太慢，参数调整可能太耗时等。
还有其他成功的方法。全部在开源项目中实现：
- 基于约束的方法
- 在UniTime中实施（并非真正适用于学校）
- 您还可以更进一步并使用整数编程。使用商业软件（ILOG CPLEX）在乌迪内大学和拜罗伊特大学（我参与其中）成功完成
- 基于规则的启发式方法 - 请参阅Drools 规划器
- 不同的启发式方法 - FET和我自己的
有关时间表软件列表，请参见此处
于 2012-05-04T08:18:04.690 回答
1
这个问题在我工作的地方是巨大的——想象一下 1800 个科目/模块和 350 000 名学生，每个人做 5 到 10 个模块，并且你想在 10 周内建立一个考试，其中试卷的时间为 1 小时到 3 天……一个加分点 - 所有考试都在线，但又糟糕，不能超过系统的最大 5k 并发负载。所以是的，我们现在正在云中扩展服务器上执行此操作。我们使用的“解决方案”只是简单地对模块排序，以了解它们与降序“冲突”的其他模块（学生两者都做），并“打包”它们，允许这些长篇论文实际上重叠，否则它根本不能做完了。所以当事情变得太大时，我发现这种“启发式”是实用的……至少。
于 2021-07-29T08:31:04.750 回答
0
我认为你应该使用遗传算法，因为：
- 它最适合大型问题实例。
- 它以不准确的答案为代价降低了时间复杂度（不是最终最好的）
- 您可以通过调整未满足的健身惩罚来轻松指定约束和偏好。
- 您可以指定程序执行的时间限制。
解决方案的质量取决于您打算花多少时间解决程序。
于 2011-01-04T15:01:31.450 回答
0
我不知道有人会同意这段代码，但我在自己的算法的帮助下开发了这段代码，并在 ruby 中为我工作。希望它会帮助那些在以下代码中搜索它的人 periodflag ，dayflag subjectflag 和 teacherflag 是具有相应 id 和标志值的哈希值，它是布尔值。有什么问题联系我.......(-_-)
periodflag.each 做 |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
于 2015-04-09T05:32:38.347 回答