30

这是我想了很久的问题。作为老师和程序员的儿子，我很早就想到了……但我仍然没有找到解决方案。

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

健全性检查

  • 一个老师不能同时教两门课
  • 学生不能同时上两节课
  • 一些教师在一周内必须至少休息一天
  • 一周中的所有日子都应包含在时间表中
  • 对象 X 每周必须有确切的时间
  • ...

优先

  • 每位教师的日程安排应尽可能紧凑（即教师应连续工作一天中的所有时间，如果可能，不得停顿）
  • 放假的老师应该能够表达对哪一天的偏好
  • 从事兼职工作的教师应该能够表达偏好是在上学的开始还是结束时工作。
  • ...

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

它被证明是NP难的吗？

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

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

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

4

10 回答 10

23

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

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

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

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

于 2008-10-16T23:57:49.920 回答
2

我认为您可能缺少一些限制。

人们希望在可能的情况下安排教师参加他们获得认证的课程。

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

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

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

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

从一小组约束开始，当你看到成功时增加它们（如果你看到成功）

可能有一种方法可以将约束与线性规划算法之类的东西结合在一起。

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

于 2008-10-16T23:42:54.723 回答
2

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

拆分问题：

  1. 创建教师、班级和偏好列表，然后让用户在地图上填充一些偏好以作为起点。
  2. 如果在列表为空之前没有通过任何健全性检查，则从列表中随机取出一个元素并将其放在地图上的随机空闲位置。如果在任何特定迭代中，您无法在不通过完整性检查的情况下将元素放置在地图上，请在地图上移动两个位置并重试。
  3. 填满地图后，尝试在地图上移动位置以优化结果。

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

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

于 2008-10-16T23:56:29.797 回答
2

回答我自己的问题：

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

关于算法的一些话：FET 使用启发式算法，依次放置活动，从最困难的开始。如果它找不到解决方案，它会将您指向潜在的不可能的活动，因此您可以纠正错误。如果可能，该算法会递归地交换活动，以便为新活动腾出空间，或者在极端情况下，回溯并切换评估顺序。重要的代码在 src/engine/generate.cpp 中。请给我发电子邮件了解详细信息或加入邮件列表。我认为，该算法模仿了人类时间表的操作。

关联

跟进 Wikipedia 上由 Stringent Software 领导的“基于约束的推理”将我带到这些 页面，其中有一段有趣的段落：

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

于 2008-10-17T00:13:47.047 回答
2

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

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

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

于 2008-10-17T09:36:09.410 回答
2

这让我想起了这篇关于安排会议的博文，这里有一个视频解释。

我会怎么做：

让人口包括两件事：

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

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

适应度函数将包括：

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

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

于 2008-12-24T07:48:45.973 回答
1

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

遗传算法非常适合此类问题。一旦你想出了一个体面的染色体表示（在这种情况下，可能是一个表示所有可用类槽的向量），你就大功告成了。

不要担心在突变阶段维护完整性检查。突变是随机的。理智和偏好检查都属于选择阶段。失败的理智检查会大大降低个体的适应度，而失败的偏好只会轻微地降低适应度。

不兼容的要求完全是一个不同的问题。如果它们完全不兼容，您将得到一个不会集中在任何有用的东西上的人口。

于 2008-10-20T21:09:15.797 回答
0

祝你好运。作为一个有这种问题的父亲的儿子，是什么把我带到了我最终加入的研究小组......

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

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

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

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

不过，请相信我，这类问题的研究小组大量涌现出博士，所以你的公司非常好。

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

于 2008-12-24T08:56:31.717 回答
0

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

当我告诉一个朋友的父亲（他是一名教师），如果他没有找到合适的计划，我可以为他解决日程安排问题（这是在 1990 年左右）

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

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

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

玩得开心

于 2009-02-20T22:16:36.880 回答
0

我看到Prolog程序可以通过将它连接到数据库来解决这个问题，并且程序可以在给定一组约束的情况下使时间表读取abt“约束满足问题序言”

于 2010-05-27T12:13:16.060 回答