如何解决这个组合算法问题。

Question

我有N个人，每个人都必须参加T场考试。每场考试需要一定时间，例如30分钟（没有提前完成的情况）。考试必须在监考官面前进行。

我需要安排每个人在整个时间段内参加每个考试，并避开午餐时间，使用最少的监考官和最短的时间（即无/最少监考官空闲）。

以下是限制条件：

- 每个人不能同时身处两个地方 - 每个人必须参加每个考试一次 - 没有人应该被同一位监考官考试两次

我意识到最优解可能是NP-Complete问题，而且最好使用遗传算法来获得最佳估计（类似于这个？Seating plan software recommendations (does such a beast even exist?)）。

我知道遗传算法的工作原理，但我不知道如何以程序方式对问题进行建模，以便可以基因地操纵参数。

如果每个考试所需的时间相同，那么我会将时间段分成这些长度，并创建一个时间段与考官的矩阵，并将候选人放入其中。然而，由于每个测试的时间不一定相同，我有点不知道如何处理。

目前我正在做以下工作：

- 制作需要进行的所有“测试”列表，包括每个候选人和考试之间的测试。 - 从与测试数量相同的考官开始。 - 反复循环所有考官，对于每个考官：查找符合限制条件的未安排测试。 - 继续，直到所有可以安排的测试都已经安排完毕。 - 如果有任何未安排的测试，则增加考官数量并重新开始。

我正在寻找更好的建议来解决这个问题，因为当前感觉相当粗糙。

- Andrew Bullock

---

作业？老师和候选人的谈话听起来像是缺乏想象力的任务设置。 - Charles Stewart

问题： (a) 每个人的考试时间是否有最长限制？ (b) 结果时间表是否可以跨越多天？ (c) 在这个算法中，一天的长度是多少？ - Andrew Anderson

我认为您缺少一个约束条件：例如，一名检查员一次只能监督一个人？ - Zac Thompson

N和T的最大可能值是多少？ - MAK

此外，“使用最少的考官在最短的时间内”这个目标并不太清晰。你愿意增加多少考官来减少一单位时间？ - Dimitris Andreou

Answer 1

正如julienaubert提出的，一种解决方案（我称之为时间表）是一个元组序列（日期、学生、考官、测试），涵盖了所有相关的学生-测试组合（所有N个学生是否都参加了T次测试？）。我理解一个考官可以同时测试多个学生。否则，将需要大量的考官（至少一个考官每个学生），这一点我非常怀疑。

如果两个元组A和B冲突，则：

• 学生相同，测试不同，时间段重叠
• 考官相同，测试不同，时间段重叠
• 学生已经与考官在另一次测试中合作过

请注意，元组冲突与时间表冲突不同（后者必须另外检查重复考官问题）。

下限：

• 考官E的数量必须>=最加班学生的所有测试数量
• 总时间必须大于最加班学生测试总时长。

可以使用以下方法构建一个简单的贪心时间表：

1. 选取最忙碌的学生，随机分配测试，每个测试由不同的考官负责。可以使用一些装箱算法来重新安排测试，以便中午的时间保持空闲。这将是一个快乐的学生：他会在最短的可能时间内完成。
2. 对于其他学生，如果该学生必须参加已经安排好的任何测试，则与之前安排的测试共享时间、场地和考官。
3. 选取最忙碌的学生（即未安排测试数量最多的学生），并分配元组，以便不违反任何限制，如有必要，增加更多时间和考官。
4. 如果有任何学生有未安排的测试，请回到步骤2。

改进步骤2中所做的选择对于改进至关重要；该选择可以成为启发式搜索的基础。上述算法试图最小化所需的考官数量，以牺牲学生的时间为代价（学生可能早上参加一场考试，晚上参加另一场考试，中间不参加任何考试）。但是，它保证产生合法的解决方案。对不同的学生运行它可以用来生成遵循合法答案的GA的“起始”解决方案。

一般来说，我认为像这样的问题没有“完美的答案”，因为必须考虑到很多因素：学生希望尽量减少他们自己考试所花费的总时间，考官也是如此；我们希望最小化考官的数量，但是在一个房间里安排多少个学生与一个考官存在实际限制。此外，我们希望安排“公平”，这样没有人明显比其他人更糟糕。因此，你能做的最好的事情就是允许调整这些参数，了解结果（总时间、每个学生的幸福感、每个考官的幸福感、考试规模、感知公平性），并允许用户探索参数空间并做出明智的选择。

- tucuxi

Answer 2

我建议使用SAT求解器来解决这个问题。虽然这个问题可能是NP难的，但好的SAT求解器通常可以处理数十万个变量。你可以查看Chaff或MiniSat这两个例子。

- Keith Randall

Answer 3

以下是如何使用遗传算法对其进行建模的方法。

使用您的表示：

• N（参加考试者数）
• T（考试次数）

让个体的基因表达一个完整的预定日程安排。即，一个个体是一系列特定预订的列表：（i，j，t，d）

• i是第i个参加考试者[1，N]
• j是第j位考官[1，？]
• 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

- user348466

Answer 4

不要过早地限制自己只使用遗传算法，还有许多其他方法。

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

- starblue

Answer 5

你也可以考虑使用约束编程。看看Prolog或者更现代的逻辑编程表达方式PyKE。

- gomad