쌍으로 이루어져야하는 활동에 사람들을 스케줄링하는 알고리즘

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 일에 할당됩니다. 가능한 모든 조합이 있음에도 유의하십시오.

현재 저는 작은 팀 (6 명 - 8 명)의 경우 쌍을 "수동으로"결합하고 정렬 할 수 있지만 더 큰 팀의 경우 알고리즘을 제안하지 못했습니다.

나를 도울 수있는 알고리즘이 있습니까?

보너스 포인트 : 어떤 시점에서

는 사람은 "비활성"이 될 수있다, 그래서 그는 규칙에 따라 다른 사람으로 교체해야합니다.

대단히 감사합니다!

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. 작업의 다음 쌍은 지금까지 선택 사항이 가장 적은 쌍입니다.

이렇게하면 부재가있는 쌍을 쉽게 제거 할 수 있습니다. 가능한 쌍의 목록에서 제외하면됩니다. 그리고 누군가 돌아 오면, 지금까지 최소한의 과제로 인해 다음 순위에 올 것입니다. 이것은 작업량을 가능한 한 평형에 가깝게 유지해야합니다.

아마도 라운드 로빈보다 예측 가능성이 낮지 만 예정된 대기열에 대한 임의의 섭동으로 인해 더 잘 처리됩니다. 그것은 또한 각 선택에 대해 선형이기 때문에 더 느립니다. 라운드 로빈은 모든 것을 처리하고 따기는 일정하지만 받아 들일 수 있습니다.

해골 파이썬 코드 :

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 

가없는 팀 구성원에 대한 계정에 당신은 pick_pair에 전달 된 pairs를 필터링 할 수 있습니다.