具有调度约束和优化的黑客马拉松团队分配

Question

我正在帮助创建一个虚拟黑客马拉松的团队，大约有1000名全球参与者参加。在注册时，参与者将被要求从6个时隙(格林尼治标准时间)中选择三个首选的黑客时间。我想组成3组(或4组，其中有一个余数)，其中包含以下约束：

• 必须有3(或4)名成员
• 每个团队成员必须至少共享2次首选黑客时间
• 每个团队都应该混合部厅H 210f 211

我从登记调查中输入的数据如下所示：

| Name     | Department    | Office      | Time Slots  | 
| -------- | --------------| ------------| ------------|
| A        | Engineering   | Bangalore   | 1, 3, 6     |
| B        | Engineering   | SF          | 2, 4, 5     |
| C        | Sales         | Amsterdam   | 1, 6, 2     |
| D        | Engineering   | NYC         | 1, 6, 3     |
| E        | CX            | SF          | 5, 1, 3     |
| F        | Engineering   | SF          | 2, 5, 4     |
| G        | Engineering   | SF          | 1, 6, 3     |
| H        | Product       | Bangalore   | 2, 4, 5     |
| I        | Product       | SF          | 1, 4, 3     |

我想要的输出是一个csv文件，如下所示：

| Team Name | Team Members   | Shared Time Slots |
| --------- | -------------- | ------------------|
| Team A    | A, C, G        | 1, 6              |     
| Team B    | B, F, H        | 2, 4              |
| Team C    | D, E, I        | 1, 3              |

因为我愿意用找到最优的解决方案来换取一个更容易实现的解决方案，所以我考虑了基于this post的随机重新启动爬山。我的问题是：

什么是一般的问题，这样我才能做更有见地的研究? hill-climbing?

• If

• 有比爬山更好的解决方法吗?如何表示公用函数中共享时隙的硬约束？。

Answer 1

这里有一个相对简单的算法，它应该适用于所有输入，但最不正常的输入除外。

1. 有两个时隙{1、2、3、4、5、6}的15个组合。对于每一个组合，构建一个参与者的垃圾箱(所以15个桶)。循环遍历所有参与者，并将它们添加到它们兼容的每个桶中(这样每个参与者都可以在多个回收箱中)。

对于每个bin，还初始化一个空列表，其中包含从该bin.构造的组。

1. 选择组列表最短的垃圾桶，如果tie中参与者最少(忽略垃圾桶中的<3参与者)。使用任何贪婪的软约束算法，从这个垃圾桶中挑选一个‘多样化’(就部门/办公室而言)组，由3名参与者组成。

将此组添加到所选回收站的组列表中，并从all回收箱中移除选定的参与者。

重复这一步骤，直到所有回收箱都剩下两个或更少的成员(或者直到构建的组不够多样化，尽管这有更高的失败机会)。

此时，

1. 只剩下几个未分组的参与者。以某种贪婪的方式将它们一个接一个地添加到任何兼容大小的三组中(例如，只需选择最大的多样性得分组)。