创建学校时间表的算法
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我一直想知道是否有有关创建学校时间表的算法的已知解决方案。基本上，它是针对给定的课堂教师协会优化“小时分散”（在教师和班级案例中）。我们可以假设我们有一组课程，课程学科和教师在输入中相互关联，并且时间表应在上午8点至下午4点之间适合。
我想可能没有准确的算法，但是也许有人知道开发它的近似值或提示。
解决方案
这个问题是 NP完整!
简而言之，需要探索所有可能的组合，以找到可接受的解决方案列表。由于在各个学校出现问题的情况下的变化（例如：关于教室的限制吗？等等）没有一个知名的问题类，它与所有调度问题相对应。也许， 背包问题 与这些问题相似，有许多相似的要素。
确认这既是一个棘手的问题，又是人们常年寻求解决方案的问题，就是检查这个问题（长） （主要是商业）软件调度工具列表
由于涉及大量变量，其最大来源通常是教师的欲望； - ）... 不切实际地考虑列举所有可能的组合. 。相反，我们需要选择一种访问问题/解决方案空间子集的方法。
- 遗传算法, ，在另一个答案中引用的是（或恕我直言， 似乎）能够执行这种半指导搜索的能力（问题是为下一代保留候选人找到一个良好的评估功能）
- 图形重写 这种类型的组合优化问题也可以使用。
我想建议 一些可以应用的策略， 在问题的定义级别.
一般的理由是，在大多数现实世界的调度问题中，将需要一些妥协，而不是所有的约束，暗示和暗示：将完全满足。因此，我们通过：
- 定义和排名所有已知约束
- 通过手动减少问题空间，提供一组 额外的 约束。
这似乎是违反直觉的，但例如，通过提供最初的，部分填充的时间表（例如，大约30％的时间插槽），以完全满足所有约束的方式，并考虑到这一部分时间表不可或缺，我们大大减少了生产候选解决方案所需的时间/空间。
另一种其他约束帮助是例如，“人为地”添加一个约束，该约束阻止在一周的某些日子（如果是每周时间表...）；这种类型的约束导致减少问题/解决方案空间，通常不包括大量好的候选者。 - 确保可以快速计算问题的某些约束。这通常与用于表示问题的数据模型的选择有关。这个想法是能够快速选择（或修剪）一些选项。
- 重新定义问题并允许某些约束被打破几次（通常朝图形的末端节点）。这里的想法是删除 一些 填写时间表中的最后几个插槽的限制，或者让自动计划生成器程序停止完成整个时间表，而是为我们提供了十几个左右的候选人列表。正如所指出的那样，人类通常处于更好的位置，可以使用通常与自动逻辑共享的信息（例如“下午没有数学”规则“有时可能会破坏规则”对于“高级数学和物理学”课；或“打破琼斯先生的要求之一，比史密斯女士之一... ;-)）
在验证这个答案时，我意识到这很害羞地提供了明确的回答，但它仍然充满了实用的建议。我希望这对毕竟是一个“严重问题”的帮助。
其他提示
一团糟。皇家一团糟。为了增加答案，我想指出我的家庭经历。我的母亲是一名老师，曾经参与这一过程。
事实证明，拥有计算机不仅很难代码，而且很困难，因为有些条件很难指定为预熟的计算机程序。例子：
- 一位老师在您的学校和另一家学院教书。显然，如果他在10.30结束课程，他将无法从您的场所开始10.30，因为他需要一些时间在研究机构之间上下班。
- 两名老师已婚。总的来说，如果不在同一班上有两名已婚老师，这被认为是好练习。因此，这两位老师必须有两个不同的班级
- 两名老师已婚，他们的孩子上同一所学校。同样，您必须防止两位老师在特定班级中教他们的孩子所在的地方。
- 学校拥有单独的设施，例如上课的一天在一个学院，另一天班上在另一个学院。
- 学校拥有共享实验室，但是这些实验室仅在某些工作日可用（例如，出于安全原因，需要其他人员）。
- 有些老师对免费一天有偏爱：有些是星期一，有些是在星期五，有些是在星期三的。有些人更喜欢在清晨来，有些人更喜欢以后来。
- 您不应该有这样的情况，您可以说，在第一个小时，然后是数学三个小时，然后是历史小时。这对学生或老师没有意义。
- 您应该均匀地传播论点。只有一周中的第一天只有数学，然后在本周的其余时间才是没有意义的。
- 您应该连续两个小时给一些老师进行评估测试。
如您所见，问题不是NP完整的，而是NP-Insane。
因此，他们要做的是，他们有一张带有小塑料插图的大桌子，然后将插图移动到获得令人满意的结果。他们从不从头开始：它们通常从上一年的时间表开始并进行调整。
这 国际时间表竞赛2007 有一个课程安排轨道和考试计划轨道。许多研究人员参加了这项比赛。尝试了许多启发式方法和元启发式学，但最终，本地搜索元启发式学（例如禁忌搜索和模拟退火）清楚地击败了其他算法（例如遗传算法）。
看看一些决赛入围者使用的两个开源框架：
- JBOSS OPTAPLANNER （Java，开源）
- 单一时间 （Java，开源） - 更多适用于大学
我的半年任务之一是遗传叠加的学校餐桌。
整桌是一个“有机体”。通用遗传算法方法有一些变化和警告：
制定了“非法表”的规则：在同一课堂上的两个课程，一位老师同时教两组等。这些突变立即被视为致命，并立即将新的“有机体”芽起来，代替“死者”。最初的一个是由一系列随机尝试生成的，以获得合法（如果毫无意义）。致命的突变没有计入迭代中突变计数。
“交换”突变比“修改”突变更为普遍。改变只有在基因的部分之间有意义的 - 没有教师用教室代替老师。
分配了小额奖金，用于将某些2个小时捆绑在一起，以分配同一小组的同一通用教室，以保持教师的工作时间和课堂'负载连续。分配了适度的奖金，用于给定学科的正确教室，将上课时间保持在债券（早上或下午）等等。最大的奖金是为了分配正确数量的给定主题，给予教师的工作量等。
老师可以创建“想要工作”，“可以工作”，“不喜欢工作”，“无法工作”的工作负载时间表，然后分配适当的权重。整个24小时都是法律工作时间，除了夜间不希望的。
重量功能...哦，是的。重量函数是分配给选定特征和属性的权重的巨大，可怕的产品（如乘法）。它非常陡峭，一个属性很容易通过上下的数量级来改变它 - 一个生物体中有数百或数千个特性。这导致了重量的绝对数量，并且作为直接结果，需要使用Bignum库（GMP）执行计算。对于大约10个组，10个老师和10个教室的小型测试柜，初始设置以10^-200s的注意事项开始，并以10^+300s的成绩完成。当它更平坦时，这是完全低效的。此外，与更大的“学校”相比，这些价值越来越远。
明智的计算时间，很长一段时间内的人口（100）与几代人的人口（10k+）之间几乎没有差异。同一时间的计算产生的质量相同。
该计算（在1GHz CPU上）将需要大约1H才能稳定在10^+300附近，生成的时间表看起来很不错，对于所述10x10x10测试用例。
通过提供可以在运行计算的计算机之间交换最佳标本的网络设施，可以很容易地排列问题。
最终的节目从未见过日光外面的日光，让我成为学期的良好成绩。它表现出了一些希望，但我从来没有足够的动力来添加任何GUI并使其可用于公众。
这个问题比看起来要严重。
正如其他人所提到的那样，这是一个NP完整的问题，但让我们分析这意味着什么。
基本上，这意味着您必须查看所有可能的组合。
但是“看”并不是告诉您您需要做什么。
生成所有可能的组合很容易。它可能会产生大量数据，但是您不应该有太多问题理解该问题的概念。
第二个问题是判断给定可能的组合是好，坏还是比以前的“好”解决方案更好。
为此，您不仅需要“可能的解决方案”。
例如，同一位老师每周5天工作5天吗？即使这是一个有效的解决方案，它也不比两个人之间的交替更好，因此每个老师每周都会做一个星期。哦，你没有考虑吗？请记住，这是您要处理的人，而不仅仅是资源分配问题。
即使一位老师可以连续16周全职工作，与您尝试在教师之间交替的解决方案相比，这可能是一个最佳的解决方案，而且这种平衡很难在软件中构建。
总而言之，对于许多人来说，为这个问题提供一个很好的解决方案将非常有价值。因此，分解和解决并不是一个容易的问题。准备好起步一些目标，这些目标不是100％，并称它们为“足够好”。
更新：从评论...也应该有启发式方法！
我会选择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硬性问题更加容易。
遗传算法通常用于这种调度。
成立 此示例（使用遗传算法制定课程时间表） 与您的需求相匹配。
我的时间表算法，在FET中实现（免费时间表软件， http://lalescu.ro/liviu/fet/ ，成功的应用程序）：
该算法是启发式的。我将其命名为“递归交换”。
输入：一组活动A_1 ... A_N和约束。
输出：一组times ta_1 ... ta_n（每个活动的时间插槽。为简单起见，在这里排除了房间）。该算法必须将每个活动都放在时间插槽中，以尊重约束。每个TA_I在0（T_1）和MAX_TIME_SLOTS-1（T_M）之间。
约束：
C1）基本：一对无法同时进行的活动列表（例如，A_1和A_2，因为他们有相同的老师或相同的学生）；
C2）许多其他约束（为简单起见，此处排除在内）。
时间表算法（我将其命名为“递归交换”）：
- 排序活动，首先最困难。并不是关键的步骤，但是加快了大概10次或更多的算法。
尝试将每个活动（A_I）放在允许的时间插槽中，一次按照上述顺序进行。搜索可用的插槽（T_J），以获取A_I，其中可以将此活动尊重约束。如果有更多的插槽，请选择一个随机的插槽。如果没有可用，请递归交换：
一个. 。对于每次插槽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）（此处使用了一些避免骑自行车的方法）。
我已经为课堂时间表和考试时间表设计了商业算法。对于第一个，我使用了整数编程；在第二个中，基于通过选择插槽互换来最大化目标函数的启发式方法，与已进化的原始手动过程非常相似。他们在接受这种解决方案的主要方面是代表所有现实世界约束的能力。并使人类时间表无法看到改善解决方案的方法。最后，与数据库的准备，用户界面，报告房间利用率，用户教育等统计信息的能力相比，算法部分非常简单且易于实现。
本文描述了学校时间表问题及其对算法的方法非常好：”教学大纲的开发 - 学校和学院的基于互动的，基于约束的调度程序。“ [PDF
作者通知我此处仍在使用/开发课程大纲软件： http://www.scientia.com/uk/
我使用广泛使用的调度引擎工作，这是这样做的。是的，它是NP完整的；最好的方法试图近似最佳解决方案。而且，当然，有很多不同的方法可以说出哪一种是“最好的”解决方案 - 例如，您的老师对他们的时间表感到满意，或者学生参加所有课程吗？
您需要尽早解决的绝对最重要的问题是 是什么使一种方法比另一个方法更好？也就是说，如果我有琼斯夫人在8岁时教数学的时间表，而史密斯先生在9岁时教数学，那比他们俩在10岁时教数学的人要好坏吗？琼斯夫人在8岁时教书和琼斯先生在2岁时教书好还是坏？为什么？
我在这里给出的主要建议是尽可能多地解决问题 - 当然，也许是老师，也许是在房间的房间里 - 并首先解决问题。在那里，您应该选择多种解决方案，并且需要选择最可能的解决方案。然后，致力于使“较早”的子问题考虑到后来的子问题在得分其潜在解决方案时的需求。然后，也许在您进入“没有有效的解决方案”状态时，也可以研究如何摆脱涂漆的情况（假设您在早期的子问题中无法预料这些情况）。
本地搜索优化通行证通常用于“抛光”最终答案，以获得更好的结果。
请注意，通常我们在学校安排中处理高度资源受限的系统。学校没有很多空的房间或坐在休息室中的75％的老师们度过一年。在解决方案环境中最有效的方法不一定适用于学校日程安排。
通常，约束编程是解决此类调度问题的好方法。搜索堆栈溢出和Google中的“约束编程”和调度或“基于约束的调度”将产生一些良好的参考。这并非不可能 - 使用线性或整数优化等传统优化方法时，很难考虑。一个输出将是 - 是否存在满足所有要求的时间表？这本身显然很有帮助。
祝你好运 ！
我认为您应该使用遗传算法，因为：
- 它最适合大型问题实例。
- 它在不准确的答案价格上降低了时间复杂性（不是最终的最好的）
- 您可以通过调整未满足的适应性惩罚来轻松指定约束和偏好。
- 您可以指定程序执行时间限制。
解决方案的质量取决于您打算花多少时间解决程序。
我不知道有人会同意此代码，但是我在自己的算法的帮助下开发了此代码，并且在Ruby中为我工作。主题Flag和Teacherflag是具有相应ID和标志值布尔值的哈希。任何问题与我联系........（-_-）
ofendflag.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
