can*_*and 88 language-agnostic algorithm np
我一直想知道是否有创建学校时间表算法的已知解决方案.基本上,它是关于优化给定班级 - 学科 - 教师协会的"小时分散"(在教师和班级案例中).我们可以假设我们在输入中有相互关联的课程,课程科目和教师,并且时间表应该适合在上午8点到下午4点之间.
我想可能没有准确的算法,但也许有人知道一个很好的近似或开发它的提示.
mjv*_*mjv 81
这个问题是NP-Complete!
简而言之,需要探索所有可能的组合以找到可接受的解决方案列表.由于问题出现在各个学校的情况有所不同(例如:教室是否存在限制？有些课程的某些课程在某些时间是分开的吗？这是一个每周安排吗？不存在对应于所有调度问题的众所周知的问题类.也许,背包问题与这些问题有很多相似之处.
确认这既是一个难题,也是人们常年寻求解决方案的问题,就是检查(长期)(主要是商业的)软件调度工具列表
由于涉及大量变量,其中最大的来源通常是教师的愿望; - )......,考虑列举所有可能的组合通常是不切实际的.相反,我们需要选择一种访问问题/解决方案空间子集的方法.
- 遗传算法,在另一个答案中引用(或者,恕我直言,似乎)很好地执行这种半导向搜索(问题是找到一个好的评估函数,为下一代保留候选人)
- 图重写方法也适用于这种类型的组合优化问题.
我不想专注于自动调度生成器程序的特定实现,而是想在问题定义的层面上提出一些可以应用的策略.
一般的理由是,在大多数现实世界的调度问题中,需要一些妥协,而不是所有的约束,表达和暗示:将完全满足.因此,我们帮助自己:
在校对这个答案的过程中,我意识到提供一个明确的答案是非常害羞的,但它却充满了实用的建议.我希望这有帮助,毕竟这是一个"难题".
Ste*_*ini 46
一团糟.皇家一团糟.为了增加答案,已经非常完整,我想指出我的家庭经历.我的母亲是一名教师,曾经参与过这个过程.
事实证明,拥有一台计算机这样做不仅难以编码本身,而且也很困难,因为有些条件很难指定给预先计算机的程序.例子:
正如你所看到的,问题不是NP完全,它是NP-insane.
所以他们所做的是他们有一个带有小塑料插入物的大桌子,他们移动插图直到获得令人满意的结果.他们从不从头开始:他们通常从上一年的时间表开始并进行调整.
Geo*_*met 24
在国际竞争排课2007年有一个教训调度跟踪和考试安排的轨道.许多研究人员参加了那场比赛.尝试了大量的启发式和元启发式算法,但最终本地搜索元启发式(如禁忌搜索和模拟退火)明显优于其他算法(如遗传算法).
看看一些决赛入围者使用的2个开源框架:
SF.*_*SF. 16
我的一个半学期任务是遗传算法学校表生成.
整个桌子是一个"有机体".通用遗传算法方法有一些变化和警告:
制定了"非法表格"的规则:同一教室的两个班级,一个教师同时教授两个班级等.这些突变立即被认为是致命的,并立即发出一个新的"有机体"代替"死者".最初的一个是由一系列随机尝试产生的,以获得合法的(如果没有意义).致死突变未计入迭代中的突变计数.
"交换"突变比"修改"突变更常见.变化只发生在有意义的基因部分之间 - 没有教师替代教室.
为了保持教师的工作时间和班级负荷连续,为同一组分配相同的通用教室,分配了小额奖金,用于捆绑约2小时.分配适度的奖金用于为给定的主题提供正确的教室,将课时保持在债券(上午或下午)等等.由于教师的工作量很大,因此可以分配正确数量的给定主题.
教师可以创建他们的工作量时间表"当时想要工作","当时可以工作","不喜欢工作","当时不能工作",并分配适当的权重.整个24小时是法定工作时间,除了夜间非常不受欢迎.
重量函数......哦是的.权重函数是分配给所选特征和属性的权重的巨大,巨大的产品(如乘法).它非常陡峭,一个属性很容易将其改变一个数量级的上升或下降 - 并且在一个生物体中有数百或数千个属性.这导致绝对巨大的数字作为权重,并且作为直接结果,需要使用bignum库(gmp)来执行计算.对于一个包含10个小组,10个教师和10个教室的小型测试用例,初始设置以10 ^ -200something的注释开始,并以10 ^ + 300something结束.当它更平坦时,效率非常低.此外,与更大的"学校"相比,这些价值观的距离越来越大.
计算时间方面,很长一段时间内的小人口(100人)和较少人口的人口(10k +)之间几乎没有差别.在同一时间的计算产生大约相同的质量.
对于所述10x10x10测试用例,计算(在一些1GHz CPU上)将花费大约1h来稳定在10 ^ + 300附近,产生看起来相当不错的时间表.
通过提供可在运行计算的计算机之间交换最佳样本的网络设施,该问题很容易解决.
由此产生的计划从来没有看到日光以外让我在这个学期取得好成绩.它显示了一些承诺,但我没有足够的动力来添加任何GUI并使其可用于普通公众.
这个问题比看起来更难.
正如其他人所提到的,这是一个NP完全问题,但让我们分析一下这意味着什么.
基本上,这意味着您必须查看所有可能的组合.
但"看看"并没有告诉你你需要做什么.
生成所有可能的组合很容易.它可能会产生大量数据,但您在理解这部分问题的概念时应该没有太多问题.
第二个问题是判断给定的可能组合是好还是差,还是比以前的"好"解决方案更好.
为此,您需要的不仅仅是"它是一种可能的解决方案".
例如,同一位老师每周工作5天,连续X周？即使这是一个有效的解决方案,它可能不是一个比两个人之间交替更好的解决方案,以便每个老师每个人做一个星期.哦,你没想到这个？请记住,这是您正在处理的人,而不仅仅是资源分配问题.
即使一位教师可以连续工作16周全职,也可能是一个次优的解决方案,相比之下,您尝试在教师之间进行替代,这种平衡很难构建到软件中.
总而言之,对许多人来说,为这个问题提供一个很好的解决方案将是值得的.因此,分解和解决并不是一个容易的问题.准备好放弃一些不是100%的目标,并称它们"足够好".
小智 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) Basic：不能同时进行的活动对的列表（例如，A_1 和 A_2，因为他们有相同的老师或相同的学生）；
C2) 许多其他约束（为简单起见，此处排除）。
时间表算法（我将其命名为“递归交换”）：
尝试按照上述顺序将每个活动 (A_i) 放在允许的时间段中，一次一个。搜索 A_i 的可用插槽 (T_j)，可以在其中放置此活动并遵守约束。如果有更多插槽可用，请随机选择一个。如果没有可用，请进行递归交换：
一个。对于每个时隙 T_j，考虑将 A_i 放入 T_j 会发生什么。将有一个不同意此移动的其他活动的列表（例如，活动 A_k 与 A_i 位于同一插槽 T_j 并且与 A_i 具有相同的老师或相同的学生）。保留每个时隙 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 步开始计算的递归调用总数）不是太大，比如 2*n），如第 2 步）。
电子。如果成功放置A_p、A_q、A_r，则成功返回，否则尝试其他时隙（转到步骤2b）并选择下一个最佳时隙）。
f . 如果所有（或合理数量的）时间段都尝试失败，则返回但不成功。
克。如果我们在第 0 级，并且我们没有成功放置 A_i，则按照步骤 2 b) 和 2 c) 放置它，但不要递归。我们现在还有 3 - 1 = 2 个活动要放置。转到步骤 2)（此处使用了一些避免循环的方法）。
更新:来自评论......也应该有启发式方法!
我会选择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问题变得更容易.