具有调度约束和优化的黑客马拉松团队分配
Hackathon team assignment with scheduling constraints and optimization
我正在帮助创建一个虚拟黑客马拉松团队，全球参与者约有 1000 人。在注册时，参与者将被要求从六个时间段（格林威治标准时间）的列表中选择三个首选的黑客攻击时间。我想组成 3 人（或 4 人，如果有剩余）的团队，但有以下限制：
- 团队必须有 3（或 4）名成员
- 每个团队成员必须分享至少 2 个首选黑客时间
- 理想情况下，每个团队都应该有部门和办公室的组合
我从注册调查中输入的数据如下所示：
| 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 的随机重启爬山。我的问题是：
- 一般 class 这属于什么问题，以便我可以进行更明智的研究？
- 有没有比爬山更好的解决方案？
- 如果爬山确实是可行的方法，我如何在效用函数中表示共享时隙的硬约束？
这是一个相对简单的算法，应该适用于除最反常的输入之外的所有输入。
两个时隙{1,2,3,4,5,6}共有15种组合。对于每个组合，构建一个 bin 参与者（因此 15 个 bin）。遍历所有参与者并将它们添加到与它们兼容的每个容器中（因此每个参与者都可以在多个容器中）。
对于每个 bin 还初始化一个空列表，其中包含从该 bin 构造的组。
Select 具有最短组列表的 bin，如果出现平局则参与者最少（忽略参与者少于 3 人的 bin）。使用任何贪婪的软约束算法从这个箱子中挑选一个 'diverse'（根据 departments/offices）组 3 名参与者。
将此群组添加到所选垃圾箱的群组列表中，并从 所有 个垃圾箱中删除所选参与者。
重复此步骤，直到所有箱子只剩下 2 个或更少的成员（或者直到构建的组不够多样化，尽管这有更高的失败机会）。
此时您只剩下几个未分组的参与者。以某种贪婪的方式将它们一个一个地添加到任何兼容的大小三组中（例如，只需选择最大化多样性分数的组）。
我正在帮助创建一个虚拟黑客马拉松团队，全球参与者约有 1000 人。在注册时，参与者将被要求从六个时间段（格林威治标准时间）的列表中选择三个首选的黑客攻击时间。我想组成 3 人（或 4 人，如果有剩余）的团队，但有以下限制：
- 团队必须有 3（或 4）名成员
- 每个团队成员必须分享至少 2 个首选黑客时间
- 理想情况下，每个团队都应该有部门和办公室的组合
我从注册调查中输入的数据如下所示：
| 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 的随机重启爬山。我的问题是：
- 一般 class 这属于什么问题，以便我可以进行更明智的研究？
- 有没有比爬山更好的解决方案？
- 如果爬山确实是可行的方法，我如何在效用函数中表示共享时隙的硬约束？
这是一个相对简单的算法，应该适用于除最反常的输入之外的所有输入。
两个时隙{1,2,3,4,5,6}共有15种组合。对于每个组合，构建一个 bin 参与者（因此 15 个 bin）。遍历所有参与者并将它们添加到与它们兼容的每个容器中（因此每个参与者都可以在多个容器中）。
对于每个 bin 还初始化一个空列表，其中包含从该 bin 构造的组。
Select 具有最短组列表的 bin，如果出现平局则参与者最少（忽略参与者少于 3 人的 bin）。使用任何贪婪的软约束算法从这个箱子中挑选一个 'diverse'（根据 departments/offices）组 3 名参与者。
将此群组添加到所选垃圾箱的群组列表中，并从 所有 个垃圾箱中删除所选参与者。
重复此步骤，直到所有箱子只剩下 2 个或更少的成员（或者直到构建的组不够多样化，尽管这有更高的失败机会）。
此时您只剩下几个未分组的参与者。以某种贪婪的方式将它们一个一个地添加到任何兼容的大小三组中（例如，只需选择最大化多样性分数的组）。