9

我需要开发一个课程时间表软件,它可以有效地分配时间段和房间。这是基于课程的例行程序,而不是基于注册后的程序。并且有效地意味着根据员工的时间偏好为课程分配时间段,并且还需要最大限度地减少第一年和第二年的课程重叠,以便第二年的学生可以重新参加他们未能通过的课程。(以及第三年和第四年的对) .

现在,起初我认为这将是一个简单的问题,但现在似乎不同了。我看过的大多数论文都使用遗传算法/PSO/模拟退火或这些类型的算法。而且我仍然无法将问题解释为 GA 问题。我感到困惑的是为什么几乎没有人建议 DFS 或图形着色算法?

如果使用 DFS/图形着色,有人可以解释这种情况吗?或者为什么不建议或尝试它们。

4

2 回答 2

2

我为一个复杂的部门解决这个问题的经验是,硬约束(比如同一人群所学的课程没有重叠,以及教师的硬约束)很容易通过精确的方法解决。我使用 0-1 整数线性规划对问题进行建模,并使用名为 minisat+ 的基于 SAT 的工具解决了这个问题。像 cplex 这样的竞争性商业工具也可以解决它。因此,使用今天的工具,即使输入相当大,也不需要像上面建议的那样进行近似。现在,优化解决方案是另一回事。可以有许多(加权)目标,并且找到使目标最小化的解决方案在计算上确实非常困难(我尝试过的任何工具都无法在 24 小时内解决它),

于 2013-07-06T00:33:20.757 回答
0

本文档描述了将 GA 方法应用于大学时间表,因此它应该直接适用于您的要求: 使用 GA 解决大学时间表

于 2012-12-06T18:14:13.583 回答