将人们安排到应该成对完成的 activity 的算法

Question

每天有一个任务需要两个人执行，并且有一个团队可用。

我们的想法是将每个可能的组合至少分配一次的方式分配给两个不同的人。

此外，理想情况下，任何特定的人都应尽可能远离前一天指定的日期。

示例：

给出的团队：A、B、C、D、E、F

任务的时间表可以是：

Day 1  = A, D
Day 2  = B, E
Day 3  = C, F
Day 4  = A, E
Day 5  = B, F
Day 6  = C, D
Day 7  = A, F
Day 8  = B, D
Day 9  = C, E
Day 10 = E, D
Day 11 = B, E
Day 12 = C, A
...

注意同一个字母的赋值距离上一次有一定的距离。例如，A 被分配到第 1、4、7、12 天，D 被分配到第 1、6、8、10 天。另请注意，所有可能的组合都存在。

目前，我可以 "manually" 对小型团队（6 - 8 人）进行合并和排序，但对于更大的团队，我还没有想出算法。

是否有算法可以帮助我？

积分：

任何时候，一个人都可以变成"inactive"，所以他应该按照规则由其他人代替。

非常感谢！

Answer 1

Wikipedia 中描述的以下 round-robin 调度算法解决了您问题的 non-bonus 部分。这个想法是配对像

0 1 2 3 4
5 6 7 8 9

得到对05 16 27 38 49，然后顺时针旋转除了0

0 5 1 2 3
6 7 8 9 4

得到对06 57 18 29 34，然后重复

0 6 5 1 2
7 8 9 4 3

等虽然这个算法是为并行 round-robin 锦标赛设计的，但它恰好有属性因为顺时针旋转不会将任何元素水平移动很远，所以每个特定数字出现之间的间隔相当大一致。

为了回答您的奖励问题，我建议您尝试使用本地搜索——随机中断不可能让任何 ahead-of-time 组合解决方案正常工作。

Answer 2

我的做法是这样的

使用组合学得到所有团队成员对。
跟踪每个成员完成任务的 how-many 次。
该任务的下一对是迄今为止选择次数最少的一对。

这样，很容易消除成员不存在的配对，您只需将其从可能的配对列表中排除即可。当有人回来时，他们很可能会排在下一个，因为到目前为止任务最少。这应该使工作量尽可能接近平衡。

它可能不如循环法可预测，但它确实能更好地处理对计划队列的随机扰动。它也更慢，因为它对每个选择都是线性的，round-robin 什么都做，而且选择是恒定的，但我想这是可以接受的。

骨架python代码：

import itertools as it

def pick_pair(pairs):
  pair = min(pairs, key=lambda p: p[0]['count'] + p[1]['count'])
  pair[0]['count'] += 1
  pair[1]['count'] += 1
  return pair

team = [ {'name' : name, 'count' : 0} for name in range(6) ]
pairs = list(it.combinations(team,2))

day = 0
for i in range(len(pairs)):
  print("Day {}: {}".format(day, pick_pair(pairs)))
  day += 1

为了解决 team-members 不存在的问题，您必须过滤传递给 pick_pair 的 pairs。

将人们安排到应该成对完成的 activity 的算法

Algorithm to schedule people to an activity that should be done in pairs

sorting

algorithm

combinations

scheduling