Алгоритм для планирования действий людей, которые должны выполняться парами.

Question

Существует задача, которая должна выполняться двумя людьми каждый день, и есть группа людей, доступных.

Идея состоит в том, чтобы назначить двух разных людей таким задачам, чтобы каждая возможная комбинация была назначена хотя бы один раз.

Кроме того, в идеале любое конкретное лицо должно быть назначено как можно дальше от предыдущего назначенного дня.

Пример:

Учитывая команда: А, В, С, D, Е, 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. Обратите также внимание на то, что присутствуют все возможные комбинации.

В настоящее время я могу «вручную» комбинировать и сортировать пары для небольших групп (6 - 8 человек), но для больших команд мне не удалось найти алгоритм.

Есть ли алгоритм, который может мне помочь?

Bonus точка:

В любой момент человек может стать «неактивные», и поэтому он должен быть заменен кем-то другим, следуя правилам.

спасибо!

Answer 1

Следующий циклический алгоритм планирования, описанный на Wikipedia, решает не-бонусную часть вашего вопроса. Идея заключается в том, чтобы соединить как

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 

и т.д. Хотя этот алгоритм был разработан для параллельных турниров с круговым движением, это имеет свойство, потому что вращение по часовой стрелке не выполняется «Не перемещайте какой-либо элемент очень далеко по горизонтали, промежутки между вхождениями каждого конкретного числа достаточно согласованы.

Чтобы ответить на ваш вопрос о бонусе, я бы рекомендовал экспериментировать с локальным поиском - нет никаких оснований для того, чтобы случайные сбои позволяли правильному комбинаторному решению.

Answer 2

Мой подход подобен этому.

1. Используйте комбинаторика, чтобы получить все пары членов команды.
2. Следите за тем, как много раз каждый участник выполнял задание.
3. Следующая пара для задания - это тот, у кого меньше всего выбора.

Таким образом, легко удалить пары с отсутствующими членами, вы просто исключите их из списка возможных пар. И когда кто-то вернется, они, вероятно, будут в очереди в очереди из-за наименьшего числа заданий. Это должно держать работу как можно ближе к equlibrium.

Это, вероятно, менее предсказуемо, чем круговой робот, но он лучше справляется со случайными возмущениями в запланированную очередь. Он также медленнее, поскольку он является линейным для каждого выбора, round-robin делает все, а выбор является постоянным, но, я думаю, это приемлемо.

Скелет код питона:

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 

Для учета отсутствующих членов команды вы должны фильтровать pairs переданную pick_pair.