调度算法/问题

Question

我很无聊,这个问题再次困扰着我.回到大学时,我常常想知道他们如何安排考试.能够安排10k学生在2周内完成考试,并保证没有学生连续两个学期参加考试.我假设应用某种形式的启发式方法.

我今晚很无聊,如果你给我合适的工具,我会在今晚到周末工作

欢呼,dassouki

编辑1: 我想我们所知道的假设如下:

1. 学生人数和他们每个人注册的课程
2. 考试期间的点数

Answer 1

这是一个着名的计算机科学问题(考试调度问题),已知是NP难的.你可能无法在周末解决它.

Answer 2

我知道这对于SO来说是偏离主题的,但是我的大学只是安排了与课堂时间相匹配的考试.所以,每个下午1点20分有MWF班级的人都在15日下午1点参加考试.由于您不能同时参加两门课程,因此无法进行考试冲突.

Answer 3

这是约束满足问题的一个例子,这是一类困难的问题.其中一些人在NP级.存在大型商业软件包用于尝试解决这些问题(例如CPLEX) - 并且通常,它们使用一些数学和许多启发式算法.