老师时间表计算法

Question

这是我长时间在脑海里想的一个问题。作为老师和程序员的儿子，早在我看来......但我仍然没有找到解决方案。

所以这是问题所在。需要使用一些限制条件为学校创建时间表。这些通常分为两类：

完整性检查

• 一位教师在同一时间
• 的学生无法遵循两个教训，同时不能教两个班
• 有的教师每周必须至少休息一天
• 本周的所有日子都应该包含在时间表
• 主题X每星期
• 必须恰好某某小时左右...

首

• 每个老师的进度安排应该尽可能紧凑型（即老师应该连续工作一整天，如果可能的话不间断）
• 有休息日的教师应该能够表达对哪一天的偏好
• 兼职工作的教师应该能够表达是在上课还是在上课结束时工作的首选。
• ...

现在，几年后没有找到一个解决方案（在此期间...学习一两件事），我意识到，这闻起来像一个NP-hard问题。

是它证明是NP难？

有没有人对如何破解这件事情的想法？

看着this问题让我思考这个问题，以及是否遗传算法是在这种情况下使用。然而，在保持完整性检查规则的同时，改变可能性是相当困难的。此外，我不清楚如何区分不兼容的要求。

---

一个小的附录，以更好地指出问题。这适用于意大利学校风格的教室，所有学生都有不同的班级（例如：第1年A部分），老师在班级之间转移。所有同班同学都有相同的时间表，无法选择参加哪一课。

Answer 1

我是开发人员之一，在学生信息系统的调度程序部分工作。 在调度问题的原始方法中，我们研究了遗传算法来解决约束满足问题，尽管我们最初取得了成功，但我们意识到解决问题的方法并不复杂（参加学校调度研讨会后）

我们目前的实施效果很好，并且使用蛮力和智能启发式技术在短时间内获得有效的时间表。考虑到每个教师的所有约束条件，同时最大限度地减少学生冲突的可能性（根据他们的课程要求），首先要制定主日程安排（向老师分配班级）。然后使用相同的方法在课堂上安排学生。

这样做可以使机器首先制定主时间表，然后根据需要进行人工调整。

调度当前实现是用Perl编写的，但我们月初访问了其他的选择上是序言和CLIPS（专家系统）

Answer 2

我想你可能会丢失一些限制。

人会愿意在可能的情况有计划为他们的认证课程的教师。

人会怀疑，在每所请求的类，以及预期人数会显著。

我认为首先要列出所有约束条件，找出表示它们的数据结构。

然后创建某种引擎来构建试用解决方案，然后根据约束评估其适用性。

然后，你可以将有趣的遗传算法部分扔在它上面，看看随着时间的推移，随着基因的混合，你是否能够增加适应度。

开始与一小的限制，并且提高它们作为你看到成功（如果你看到成功）

有可能采取的约束，并与类似的线性规划算法一起鞋拔子它们的方式。

我同意。这听起来像是一个有趣的挑战

Answer 3

这是一个映射问题： 你需要映射到一个星期的每个小时，每个老师一个活动（教给某个班级或免费小时）。

分割问题：

1. 创建的教师，班级和喜好列表，然后让用户填入一些偏好的地图上有作为出发点。
2. 从列表中随机取一个元素，并将它放在地图上的一个随机空闲位置 如果它没有跨越任何完整性检查直到列表为空。如果在任何特定的迭代中，您不能在地图上放置元素，而不通过健全检查在地图上移动两个位置，然后重试。
3. 当地图填满后，尝试在地图上移动位置以优化结果。

在步骤2和3中向用户显示每次迭代：列表中剩余的项目，地图上的位置和下一个计算出的移动，并让用户介入。

我没有试过这个，但这将是我最初的方法。

Answer 4

一个最坏的开放源代码的网页不断，但该项目前景看好： http://www.lalescu.ro/liviu/fet/

一个基于Web的形式给出：
phpScheduleIt（不是学校专用）

Answer 5

回答我的问题：

通过gnud提到的FET项目采用这种算法：关于算法

有些话：FET 采用启发式算法，将 活动又开始 最困难的。如果它不能 找到解决方案它会指向 潜在的不可能的活动，所以 您可以更正错误。算法 递归交换活动如果该 是可能的，以便为 创造一个新的活动空间，或在极端情况下， 回溯和开关顺序 评估。重要的代码是 src/engine/generate.cpp。请通过电子邮件联系 了解详情或加入邮件 列表。该算法模仿人类时间表的操作，我想 。

Link

---

跟进维基百科的“约束推理”铅通过严格的软件使我​​pages其中有一个有趣的段落：

解决约束满足 一般来说，有限域上的问题是一个NP完全问题。 研究显示了多个 多项式时间子数据库，通过限制 允许的域或约束条件或 变量的方式约束条件可以获得多数子时间子数据库，大多数为 。研究还建立了 约束满足问题与 问题在其他领域，如有限的 模型理论和数据库的关系。

Answer 6

我已经解决了过去类似的计划/调度问题，并且通常最适合这类问题的AI技术是“基于约束的推理”。

它基本上是像Laurenty所建议的那样的强力方法，但该方法涉及以有效的顺序应用约束以导致不可行的解决方案快速失败 - 以最小化所需的计算。

谷歌搜索“基于约束的推理”提出了大量关于该技术及其在调度问题中的应用的资源。

Answer 7

望着这个问题让我想起 这个问题，和遗传算法是否 将是 这种情况下使用。然而， 很难改变可能性，而 维持完整性检查规则。 另外，我不清楚如何 区分不兼容的要求。

遗传算法非常适合这样的问题。一旦你想出一个体面代表性的染色体（在这种情况下，可能是一个代表所有可用班级插槽的向量），那么你就是最重要的途径。

不要担心在突变阶段维护理智检查。突变是随机的。理智和偏好检查都属于选择阶段。健康检查失败会大大降低个人的健康水平，而失败的偏好只会适度地降低健康水平。

不兼容的要求是完全不同的问题。如果它们完全不兼容，那么你会得到一个不会聚焦于任何有用的人群。

Answer 8

这让我想起这blog post about scheduling a conference，与video explanation here。

我怎么会做：

有人口包括两件事情：

• 谁教什么课（我希望老师教一个主题）。
• 班级在特定时间段上的表现如何。

这样我们就不会有矛盾了（一个老师在2个地方，或者同时有两个科目的班级）。

健身功能将包括：

• 多少个时隙，每周每个老师给。
• 老师在同一天有多少个时间段（他们不能有一整天的教学，这也必须是平衡的）。
• 同一天同一科目有多少个时间段（他们不可能有一整天的数学！）。

由于它们应该是平衡的，所以可能采取标准差。

Answer 9

祝你好运。作为一个父亲的儿子有了这样的问题是什么带我去，我结束了在...

---

当我还是个孩子在当地的体育联盟父亲安排比赛官员调研组，这有一个类似的长长的约束列表，我试图写点东西来帮助。当我到达大学时，我甚至将其作为我最后一年的项目，最终以蒙特卡罗实现（使用模拟退火模型）来实现。

其基本思路是，如果它不是NP，它非常接近，所以不是假设有解决方案，而是着手在给定的时间范围内找到最好的。我会用所有的约束来分解它们的成本：合理性检查会产生巨大的成本，偏好会降低成本（但是如果有更多的中断会增加，所以打破它一次不到打破它两次的成本的一半）。

其基本思想是，我从一个“随机”解决方案开始，并对其进行计算;然后通过交换少量的作业进行更改，重新评估，然后按比例接受或拒绝变更。

经过数千次迭代后，您的英寸更接近可接受的解决方案。

不过，请相信我，这类问题让研究小组产生了博士学位，所以你们的公司非常好。

您可能还会对线性编程领域感兴趣，例如： simplex等。

Answer 10

我不确定这是否与@Stringent Software's答案（因为名称略有不同）相同，但我有几个非常好的朋友正在研究Constraint Programming的面积。创建时间表是他们研究的一个应用。

Dr Chris Jefferson创建了一个名为Minion程序，您可以从SourceForge下载，并求解用C++编写一个非常快的强力约束问题

Answer 11

是的，我认为这是NP完全性 - 或者至少找到最佳解决方案是NP完整的。

当我告诉一位朋友的父亲（他是一位老师）时，如果他没有找到适合自己的计划，我可以解决他的日程安排问题（我回到了1990年，所以）

我不知道自己陷入了什么。幸运的是，我所要做的就是找到一个适合这些限制的解决方案。但在我的测试中，我总是担心如果确实有解决方案。他从来没有太多限制，程序使用了不同的启发式和后向追踪。这非常有趣。

我觉得比尔盖茨在高中时也曾在高中或大学这样的系统中工作过。但不知道。

祝你好运。我所有的笔记都没有了，我从来没有想过要实施一个我可以推销的解决方案。这是一个特殊的项目，我重新编码为我学到了新的语言（基本，方案，C，VB，C++）

有乐趣

Answer 12

我看到，这个问题可以通过Prolog程序所要解决连接到数据库 和程序可以使时间表给定一组约束 阅读abt“约束满足问题序言”