logo标签列表

大学考试排课算法/问题

algorithmscheduling
6
我在想如何安排10,000名学生在两周内参加考试，并确保没有学生连续参加两个考试时段。我假设需要应用某种启发式方法。
我们所知道的是：
1. 学生人数以及他们各自注册的课程。 2. 考试时段的数量。
如果他们真的这样做了，那么情况与我上大学时有所不同——我肯定在连续的时间段内参加了一些考试。 - Jerry Coffin
1
我担心在绝大多数情况下还是手动完成的。不像每个一万个学生都有完全不同的考试题集，对吧？可能有几十个“考试组”，每个组里有多达几百名学生。如果你有足够的空间，手动安排他们应该不会成为问题。 - Joren
我只在几年前上过大学。尽管我们所有的课表系统都是电子化的，但解决时间冲突和找到管理员重新安排课程的责任落在矛盾的学生身上。该系统本身没有任何调度智能。 - ephemient
我一直怀疑他们会安排“互补”的课程，以避免冲突。也就是说，大二的电气工程专业学生很可能同时修读“电气元素”和“信号与系统”，因此它们不会被安排在同一时间上。虽然安排“信号 II”有冲突是安全的，因为大一的学生不会选修这门课。但选修课会搞乱一切（通常需要重新安排考试）。 - Marc Bernier
10个回答
17

这是一个著名的计算机科学问题（考试调度问题），已知为NP-hard。你可能无法在一个周末内解决它。

7

我知道这个问题与SO的主题无关，但我的大学安排考试的时间块与上课时间相匹配。因此，每个星期一、三、五下午1:20上课的学生在15日下午1:00参加考试。由于不能同时上两门课程，所以不可能出现考试冲突。

这是一个不错的方法，但他们仍然需要生成课程表！ - david_adler
2
他们不必担心生成课程时间表的安排！如果两个班在同一时间 - 你将无法同时上课。当然，除非你有像赫敏一样的时光转换器！！ - Hari
5

这是一个约束满足问题的示例，它属于一类困难的问题。其中一些问题属于NP类。存在大型商业软件包（例如CPLEX）来尝试解决这些问题 - 通常使用一些数学和大量的启发式方法。

一个不错的评论，但并不完全是我所说的“答案”。你有解决这个问题的建议或相关资源吗？ - San Jacinto
2
我在硕士期间使用了禁忌搜索。这个想法并不太复杂：
  1. 从一个可能的解决方案（任何一个）开始，并进行权衡（例如，如果一个学生同时参加两场考试，则扣除1000分）
  2. 只需更改几个任务即可更改该解决方案并重新计算权重
  3. 如果第二步比第一步更好，请重复以2.作为根解决方案开始

如果您被阻塞，可以通过对初始解决方案进行重要更改来“访问”其他解决方案。

1
这是图着色问题的一个应用。该问题可以表示为一个图，其中每个顶点都是一门课程，两个顶点之间的边意味着有共同的学生在两门课程中注册。因此，这是一个图着色问题，其中最少时间段的数量等于为了以这种方式对图的顶点进行着色而需要的最少颜色数，以便没有两个相邻的顶点共享相同的颜色。
1
1

虽然价格昂贵，但我曾经看到类似问题使用CPLEX。

1
问题实际上可能比那个更普遍。例如，在我的学校，考试是按照课程安排的时间表安排的 - 即通常在学期期间相同时间举行的所有课程，在考试周的某个时间段内安排了一次考试（不一定与正常课堂会议的时间相同）。因此，冲突通常不存在，因为学生显然不会在同一时间参加两个课程，因此也不会同时参加两个考试。

但是，这意味着您仍然需要安排课程，以使它们不冲突。 :)

1
当我还是大学的高年级学生时，我们在人工智能课上做了一个类似的期末项目。我们编写了一个（勉强）可行的系统，用于在适当的时间为建筑物安排课程。有一些规则是不能被违反的：如果教授需要一个多媒体教室，他就会得到一个。如果是计算机科学课程，那么就不应该安排在艺术楼里。教授之间的课程间隔不应超过2个小时等等。
我们使用了遗传算法。
1
有几件事情可以让问题变得更简单。通过查看参加相同考试的人，您可能可以将“要安排的单位”数量从数万个缩小到几百个。如果有300个人都参加“计算机科学导论”和“计算机科学专业数学”，则可以将所有300个人安排为一个单元，因为他们都具有相同的约束条件，而且您（可能）不希望在多个时间段内给出相同的考试。
1
为什么不根据每个班级的课程安排时间表呢？忘记学生，从班级层面考虑。无论是考试还是讲座，你都不能同时出现在两个地方。 - San Jacinto
主要原因是当我在大学时，除了时间外，没有什么能阻止学生参加额外的课程。再加上后来需要重修不及格考试的复杂情况，你就会陷入痛苦之中。 - Vatine
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接