•  03-07-2019
  •  | 
  •  

题

这是我心里长久以来的一个问题。作为一名教师和程序员的儿子，我很早就想到了......但我仍然没有找到解决方案。

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

健全性检查

  • 一个老师不能同时教授两个班级
  • 学生不能同时学习两节课
  • 有些老师每周必须至少休息一天
  • 时间表应涵盖一周中的所有天
  • 对象 X 每周必须有确切的某某时间
  • ...

优先

  • 每个老师的日程安排应该尽可能紧凑（即如果可能的话，老师应该连续工作一天的所有时间，不要停顿）
  • 有休息日的教师应该能够表达自己偏好的休息日
  • 兼职教师应该能够表达是否在上课开始或结束时工作的偏好。
  • ...

现在，经过几年没有找到解决方案（同时学习一两件事......），我意识到这听起来像是一个 NP 难题。

它被证明是NP困难的吗？

有人知道如何破解这个东西吗？

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

一个小附录，以更好地说明问题。这适用于意大利学校风格的教室，其中所有学生都属于不同的班级（例如：第一年 A 部分，教师在班级之间流动。同一班级的所有学生都有相同的时间表，并且无法选择参加哪些课程。

有帮助吗？

解决方案

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

我们当前的实现效果很好，并使用暴力和智能启发法在短时间内获得有效的时间表。首先制定主时间表（将课程分配给教师），考虑到每个教师的所有限制，同时最大限度地减少学生发生冲突的可能性（根据他们的课程要求）。然后使用相同的方法将学生安排在班级中。

这样做可以让机器首先构建一个主计划，然后在需要时进行人工调整。

调度程序当前的实现是用 perl 编写的，但我们早期访问过的其他选项是 Prolog 和 CLIPS（专家系统）

其他提示

这是一个映射问题：您需要映射到一周中的每个小时以及每个老师的一项活动（教授某个班级或空闲时间）。

拆分问题：

  1. 创建教师、班级和首选项列表，然后让用户在地图上填充一些首选项作为起点。
  2. 随机从列表中获取一个元素，并将其放在地图上的随机自由位置，如果它没有跨越任何理智检查，直到列表为空。如果在任何特定迭代中，您无法在不通过健全性检查的情况下将元素放置在地图上，请在地图上移动两个位置，然后重试。
  3. 当地图被填满时，尝试移动地图上的位置以优化结果。

在步骤 2 和 3 中向用户展示每次迭代：列表中剩余的项目、地图上的位置以及下一个计算出的移动，并让用户进行干预。

我没有尝试这样做，但这将是我最初的方法。

我过去解决过类似的计划/调度问题，最适合此类问题的人工智能技术通常是“基于约束的推理”。

这基本上是一种像劳伦蒂建议的蛮力方法，但该方法涉及以有效的顺序应用约束，以使不可行的解决方案快速失败 - 从而最大限度地减少所需的计算。

谷歌搜索“基于约束的推理”，可以找到大量有关该技术及其在调度问题中的应用的资源。

回答我自己的问题：

gnud 提到的 FET 项目使用了这个算法：

关于算法的一些话：场效应管 使用启发式算法，将 依次进行活动，从 最困难的。如果不能 找到一个解决方案，它将您指向 潜在的不可能的活动，所以 您可以更正错误。算法 如果那样，则递归交换活动 是可能的，以便腾出空间 一项新活动，或者在极端情况下， 回溯和切换顺序 评估。重要代码在 src/engine/generate.cpp。请发邮件 我了解详情或加入邮件 列表。该算法模拟 人类时间表的操作，I 想。

关联

跟随维基百科上严格软件领导的“基于约束的推理”，我发现 这些 页面 其中有一个有趣的段落：

通常，在有限域中解决约束满意度问题是NP完整问题。研究显示了许多多项式时间子案例，主要是通过限制允许的域或约束或可以放在变量上的约束方式获得的。研究还建立了约束满意度问题与其他领域（例如有限模型理论和数据库）的关系。

这让我想起了这个 有关安排会议的博客文章, ，有一个 视频解释在这里.

我会怎么做：

让人口包括两件事：

  • 谁教什么课（我希望老师教一门科目）。
  • 课程在特定时间段上的内容。

这样我们就不会发生冲突（一个老师在两个地方，或者一个班级同时有两个科目）。

适应度函数包括：

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

也许取所有这些的标准差，因为它们应该是平衡的。

我不确定这是否涵盖相同的领域 @严格软件 答案（因为名称略有不同），但我有几个非常好的朋友正在研究该领域 约束规划. 。创建时间表是他们研究的一项应用。

克里斯·杰斐逊博士 创建了一个名为 奴才 您可以从 SourceForge 下载，它是一个用 C++ 编写的非常快速的强力约束问题求解器

我认为您可能会错过一些限制。

人们希望尽可能让教师安排他们获得认证的课程。

人们可能会怀疑所要求的课程以及每个课程的预期人数会很大。

我认为开始的地方是列出所有的约束，找出一个数据结构来表示它们。

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

然后，您可以将有趣的遗传算法部分投入其中，看看是否可以随着基因混合而随着时间的推移而增加适应性。

从一小部分约束开始，并在看到成功时增加它们（如果您看到成功）

可能有一种方法可以接受约束并将它们与线性规划算法之类的东西硬塞在一起。

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

有史以来最糟糕的开源网页之一，但该项目看起来很有前途：http://www.lalescu.ro/liviu/fet/

基于网络的方法：
phpScheduleIt （不针对学校）

看着这个问题，我思考 关于这个问题，以及是否 遗传算法可用于 这种情况。然而，它会很漂亮 很难改变可能性，而 维护健全性检查规则。我也不清楚如何 区分不兼容的需求。

遗传算法非常适合解决此类问题。一旦你想出了染色体的适当表示（在本例中，可能是代表所有可用类槽的向量），你就已经成功了。

不要担心在突变阶段维持健全性检查。突变是随机的。健全性和偏好检查都属于选择阶段。失败的健全性检查会大大降低个人的适应度，而失败的偏好只会轻微降低适应度。

不兼容的需求完全是一个不同的问题。如果它们完全不相容，你就会得到一群不会聚集在任何有用的东西上的群体。

祝你好运。作为一个有此类问题的父亲的儿子，我加入了一个研究小组，最终我加入了……

当我还是个孩子的时候，我父亲在当地体育联盟安排了比赛官员，这也有类似的长长的限制清单，我试图写一些东西来提供帮助。当我进入大学时，我什至将其用作我的最后一年项目，最终决定采用蒙特卡罗实现（使用模拟退火模型）。

基本思想是，如果它不是 NP，那么它就非常接近，所以我不会假设存在解决方案，而是着手在给定的时间范围内找到最好的解决方案。我会用打破这些限制的成本来衡量所有限制：健全性检查将产生巨大的成本，偏好将具有较低的成本（但会增加更多的破坏，因此破坏一次的成本不到破坏两次的成本的一半）。

基本想法是，我从一个“随机”解决方案开始，并计算了它的成本；然后通过交换少量作业进行更改，重新评估它，然后概率性地接受或拒绝更改。

经过数千次迭代后，您离可接受的解决方案更近了一步。

不过，请相信我，这类问题已经有研究小组产出了博士学位，所以你们是很好的伙伴。

您可能还会对线性规划领域感兴趣，例如 单纯形 等等。

是的，我认为这是NP完全的——或者至少找到最优解是NP完全的。

我在大学时也遇到过类似的问题，当时我告诉一位朋友的父亲（他是一名老师），如果他没有找到合适的程序，我可以为他解决日程安排问题（这要追溯到 1990 年左右）

我不知道自己陷入了什么境地。对我们来说幸运的是，我所要做的就是找到一种符合限制的解决方案。但在我的测试中，我总是担心确定是否有解决方案。他从来没有太多的限制，并且该程序使用不同的启发式和回溯法。这很有趣。

我认为比尔·盖茨在高中或大学时也曾为他的高中开发过这样的系统。但不确定。

祝你好运。我所有的笔记都消失了，而且我从未抽出时间来实施可以推销的解决方案。这是我在学习新语言（Basic、Scheme、C、VB、C++）时重新编码的一个专业项目

玩得开心

我看到这个问题可以通过Prolog程序连接到数据库来解决 程序可以制定给定一组约束的时间表 阅读 abt “约束满足问题 prolog”

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top