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

Question

我N有人必须参加T考试.每次考试都需要"一些"时间,例如30分钟(没有提前完成的事情).考试必须在考官面前进行.

我需要安排每个人在整个时间段内在考官面前进行每次考试,但避免午休,在最短的时间内使用最少数量的考官(即没有/最小考官闲置)

有以下限制:

• 没有人可以同时在两个地方
• 每个人必须参加一次考试
• 没有人应该由同一位考官两次检查

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

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

如果每次考试花费相同的时间,那么我将时间段划分为这些长度,然后简单地创建一个时间矩阵与审查员并将候选人放入.但是因为每次测试的时间不一定是同样,我对如何处理这个问题有点失落.

目前我这样做:

• 列出每个候选人和考试之间需要进行的所有"测试"
• 从有尽可能多的审查员开始,有测试
• 反复遍历所有审查员,每个审查员:找到一个符合审查员资格的计划外测试(根据限制)
• 继续,直到所有可以安排的测试,是
• 如果有任何未安排的测试,请增加审查员人数并重新开始.

我正在寻找关于如何处理这个问题的更好的建议,因为它目前感觉相当粗糙.

Answer 1

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

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