6

我必须实现一种算法，为大学生成时间表。我搜索并发现了很多算法。但问题就在这里。我需要一种算法来生成整个学期的时间表，而不是每周一次。它还应该考虑课程部分的预定义顺序，例如练习1应该在第2讲之后和第3讲之前。您有什么建议吗？

谢谢。

更新：
我有以下硬性限制：
H1：在任何时间段，每个房间只分配一个课程部分。
H2：房间可以容纳所有参加的学生并满足活动要求的所有功能。
H3：没有学生同时参加的模式超过一门课程（至少是必修课）
H4：没有老师同时教超过一门课程部分。

软约束是：
S1：不应将课程部分分配给讲师不方便的时间段。
S2：老师的班级之间应该有最小数量的差距。
S3：学生的班级之间应该有最少的间隔。
S4：课程应满足讲师的偏好——天数和时间段。
S5：课程部分应按预定顺序安排。

示例：
课程“软件架构” 

Week No   Course    Room    Course Part   Day       Time
--------+---------+-------+--------------+----------+-----
Week 1:   SA        435     Lecture 1     Wednesday  8.15-11
Week 2:   SA        435     Lecture 2     Wednesday  8.15-11
Week 3:   SA        47      Lab 1         Monday     13-15
Week 3:   SA        436     Lecture 3     Wednesday  11-14
Week 4:   SA        243     Exercise 1    Monday     13-15
Week 5:   SA        436     Lecture 4     Wednesday  8.15-11
4

4 回答 4

1

您可能想研究间隔调度。听起来您需要一个修改版本，添加一些限制，例如允许放置练习的位置。贪心算法通常很容易修改，并且有一大堆已经修改过的基本 IS 算法版本。

于 2010-06-20T06:47:19.847 回答
0

我最终得到了这里建议的修改算法。我使用了迭代前向算法，然后对软约束应用了模拟退火。我更改了时间段集，使其包含整个学期的时间段集，不包括周末和节假日。例如，如果学期有 6 周，而我每周有 40 小时，那么我的时隙集将包含全部 240 个时隙。

我还为订单添加了一个约束。当不满足此约束时，它会为当前解决方案赋予较高的权重。通过这种方式，我可以防止算法选择不符合顺序的课程的解决方案。

于 2010-08-12T08:18:35.247 回答
0

我正在从事类似的项目并使用自适应遗传算法来解决手头的问题。

详细研究遗传算法，然后使用您的约束设计流程图来解决您的问题，同时考虑您提到的所有约束。

于 2013-04-12T09:17:22.637 回答
-1

IIRC 这样的问题不能完全通过算法解决。

于 2010-06-20T15:34:09.857 回答