7

我有些N人必须每个人都参加T考试。每项考试都需要“一些”时间，例如 30 分钟（没有提早完成这样的事情）。考试必须在考官面前进行。

我需要安排每个人在整个时间段内在考官面前参加每项考试，但要避免午休，在最短的时间内使用最少数量的考官（即没有/最少的考官空闲）

有以下限制：

  • 一个人不能同时在两个地方
  • 每个人必须参加一次考试
  • 任何人都不应该被同一位考官检查两次

我意识到最佳解决方案可能是 NP 完全的，并且我可能最好使用遗传算法来获得最佳估计（类似于此？座位计划软件建议（这样的野兽甚至存在吗？））。

我对遗传算法的工作方式感到满意，我正在努力解决的是如何以编程方式对问题进行建模，以便我可以通过遗传方式操纵参数。

如果每次考试花费相同的时间，那么我会将时间段划分为这些长度，并简单地创建一个时间段与考官的矩阵并将候选人放入。但是因为每次测试的时间不一定是同样，我对如何解决这个问题有点迷茫。

目前我正在这样做：

  • 列出每个考生和考试之间需要进行的所有“测试”
  • 从有多少考试开始就有多少考官
  • 重复循环遍历所有考官，每个考官：找到一个符合考官资格的计划外测试（基于限制）
  • 继续，直到所有可以安排的测试，
  • 如果有任何计划外的考试，请增加考官人数并重新开始。

我正在寻找有关如何解决此问题的更好建议，因为目前感觉相当粗糙。

4

5 回答 5

1

正如julienaubert 所建议的那样，一个解决方案（我称之为schedule）是一个元组序列（日期、学生、考官、测试），涵盖所有相关的学生-测试组合（是否所有 N 个学生都参加了所有 T 测试？）。我知道一个考官可以同时测试几个学生。否则，将需要大量的考官（每个学生至少一名），我对此表示怀疑。

如果两个元组 A 和 B 发生冲突

  • 学生相同，考试不同，时间段重叠
  • 考官相同，考试不同，时间段重叠
  • 学生已经与考官一起进行了另一项测试

请注意，元组冲突与调度冲突不同（必须另外检查重复的检查者问题）。

下限：

  • 考官人数 E 必须 >= 最过度劳累学生的考试总数
  • 总时间必须大于最过度劳累的学生的考试总时间。

可以通过以下方法构造一个简单的贪心时间表：

  1. 选择最过度劳累的学生并随机分配测试，每个测试都有不同的考官。一些垃圾箱可用于重新排序测试，以便午餐时间保持空闲。这将是一个快乐的学生：他会在尽可能短的时间内完成。
  2. 对于其他学生，如果学生必须参加任何已安排的考试，则与之前安排的考试共享时间、地点和考官。
  3. 选择最过度劳累的学生（例如：最多数量的计划外测试），并分配元组以便不违反约束，必要时增加更多时间和考官
  4. 如果任何学生有计划外的考试，请转到 2。

改进上述步骤 2 中的选择对于改进至关重要；这种选择可以构成启发式搜索的基础。上述算法试图以牺牲学生时间为代价来最小化所需的考官数量（学生可能会在早期完成一次考试，而在一天中最后一件事，两者之间没有任何关系）。但是，保证会产生合法的解决方案。与不同的学生一起运行它可用于为坚持合法答案的 GA 生成“起始”解决方案。

总的来说，我认为像这样的问题没有“完美答案”，因为有很多因素需要考虑：学生希望尽量减少自己检查自己的总时间，考官也是如此；我们希望尽量减少考官的数量，但对于一个考官可以在一个房间里堆放多少学生也有实际限制。此外，我们想让调度“公平”，所以显然没有人比其他人更糟。所以你能做的最好的事情就是让这些旋钮被摆弄，结果是已知的（总时间、每个学生的幸福感、每个考官的幸福感、考试规模、感知的公平性）并允许用户探索参数空间并做出明智的选择。

于 2010-06-03T18:01:06.777 回答
1

我建议为此使用 SAT 求解器。尽管问题可能是 NP 难题，但好的 SAT 求解器通常可以处理数十万个变量。查看Chaff或MiniSat中的两个示例。

于 2010-06-03T23:08:56.513 回答
0

以下是关于如何使用 GA 对其进行建模的方法。

使用您的符号：

  • N (nr 应试者)
  • T（NR考试）

让一个人的基因表达一个完整的预订时间表。即个人是特定预订的列表：(i,j,t,d)

  • i 是第 i 个考生 [1,N]
  • j 是第 j 个考官 [1,?]
  • t 是考生必须参加的第 t 次考试 [1,T]
  • d 是考试的开始时间（日期+时间）

使用具有以下属性的适应度函数进行评估：

  • 对所有重复预定的考官进行（严重）处罚
  • 处罚考官空闲时间
  • 对未在其时间段内分配的考生进行处罚
  • 期间预约的每位考生的考试奖励

此功能将具有确定双重预订等的所有逻辑。您有完整的个人建议时间表，您现在运行逻辑，知道每次预订的每次测试时间以确定适合度，并增加/减少分数相应的预订。

为了使这项工作顺利进行，请考虑：

  • 启动 - 如果计算成本低，请使用尽可能多的信息来进行“合理”的预订。
  • 定义适当的 GA 运算符

以理智的方式开始：

  • 时间段内随机选择d
  • 随机排列 (1,2,..,N) 然后从中选择 i （避免重复），对于 j 和 t 相同

适当的 GA 运算符：

假设您预订了 a和b : (a_i,a_j,a_t,a_d) (b_i,b_j,b_t,b_d)

您可以交换 a_i 和 b_i，也可以交换 a_j 和 b_j 以及 a_d 和 b_d，但交换 a_t 和 b_t 可能没有意义。

你也可以骑自行车，最好用一个例子来说明，如果 N*T = 4 一个完整的预订是 4 个元组，然后你会沿着 i 或 j 或 d 循环，例如沿着 i 循环：

a_i = b_i
b_i = c_i
c_i = d_i
d_i = a_i
于 2010-06-03T16:46:30.327 回答
0

不要过早地将自己局限于遗传算法，还有很多其他方法。

更具体地说，遗传算法只有在您可以将两个解决方案的一部分组合成一个新解决方案时才真正有用。对于这个问题，这看起来相当困难，至少如果有相似数量的人和考试，以便他们中的大多数人直接交互。

于 2010-06-01T19:36:01.843 回答
0

您也可以考虑约束规划。查看 Prolog，或者，对于逻辑编程的更现代的表达方式，PyKE

于 2010-06-03T22:41:46.023 回答