CODEWITHSUNDEEP
algorithmsortingcombinationsscheduling
afcastano
afcastano

Reputation: 548

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

There is a task that needs to be executed by two people every day and there is a team of people available.

The idea is to assign two different people to that tasks in a way that every possible combination is assigned at least once.

Also, ideally, any particular person should be assigned as far as possible from the previous assigned day.

Example:

Given team: A, B, C, D, E, F

The schedule for the task could be:

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
...

Note that the same letter is assigned with certain distance from the previous time. For example A is assigned to days 1, 4, 7, 12 and D is assigned to days 1, 6, 8, 10. Note also that all possible combinations are present.

Currently, I can "manually" combine and sort the pairs for small teams (6 - 8 people), but for bigger teams I haven't been able to come up with an algorithm.

Is there an algorithm that can help me?

Bonus Point:

At any point, a person can become "inactive", and so he should be replaced by someone else following the rules.

Thank you very much!

Upvotes: 2

Views: 1665

Answers (2)

luk32
luk32

Reputation: 16090

My approach is like this.

  1. Use combinatorics to get all pairs of team members.
  2. Keep track of how-many times each member did the task.
  3. The next pair for the task is the one with least amount of picks so far.

This way, it is easy to eliminate pairs with absent members, you just exclude it from the list of possible pairs. And when someone comes back, they will be likely to be next in line because of least of assignments so far. This should keep the amount of work stay as close to equlibrium as possible.

It is probably less predictable than round robin, but it does deal better with random perturbations to the planned queue. It is also slower, as it is linear for each pick, round-robin does everything, and picking is constant, but I guess it is acceptable.

Skeleton python code:

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

To account for absent team-members you have to filter the pairs passed to pick_pair.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65506

The following round-robin scheduling algorithm described on Wikipedia solves the non-bonus part of your question. The idea is to pair like

0 1 2 3 4
5 6 7 8 9

getting pairs 05 16 27 38 49, and then rotate clockwise all but 0

0 5 1 2 3
6 7 8 9 4

getting pairs 06 57 18 29 34, and then repeat

0 6 5 1 2
7 8 9 4 3

etc. Although this algorithm was designed for parallel round-robin tournaments, it happens to have the property that, because the clockwise rotation doesn't move any element very far horizontally, the gaps between occurrences of each particular number is fairly consistent.

To answer your bonus question, I would recommend experimenting with local search -- there's no way that random disruptions are going to let any ahead-of-time combinatorial solution work properly.

Upvotes: 5

Related Questions