Algorithm to assign tasks to people, where some tasks require multiple people, and no person does the same task twice

Question

A teacher friend of mine asked me to cook up a program to help them assign classroom jobs to their students. There are 23 kids and 12 different job types, where some jobs require multiple kids, totaling 23 available positions. Each week they want to randomly assign new jobs to the kids, where no kid does the same job more than once for as long as that is possible.

My thought process was to generate all possible assignments of kids to jobs following this rule, then step through the results one by one. But I am stumped trying to come up with a practical algorithm to generate these assignment combinations.

If anyone has any ideas for solutions, or can let me know I'm chasing an impossible one, I'd appreciate it!
I've pasted all the jobs and how many kids are needed for each below in case it's helpful.

"Attendance": 1,
"Table Captain": 4,
"Teacher's Helper": 2,
"Board Eraser": 2,
"Light Switcher": 1,
"Librarian": 2,
"Lunch Helper": 1,
"Equipment Manager": 3,
"Trash Monitor": 2,
"Tech Specialist": 1,
"Paper Passer": 3,
"Pencil Sharpener": 1

Answer 1

This is a trivial scheduling problem. You have 23 students for 23 slots; your largest equivalence group is 4 (Table Captain). Line them up and assign jobs. Every week, shift the kids over 4 spots. 23 and 4 are relatively prime, so the pattern won't repeat for 23 weeks.

Let's designate the job types with the ten numerals and two special characters; the students can be letters.

0 "Attendance": 1,
1 "Table Captain": 4,
2 "Teacher's Helper": 2,
3 "Board Eraser": 2,
4 "Light Switcher": 1,
5 "Librarian": 2,
6 "Lunch Helper": 1,
7 "Equipment Manager": 3,
8 "Trash Monitor": 2,
9 "Tech Specialist": 1,
# "Paper Passer": 3,
$ "Pencil Sharpener": 1

Schedule:

 job    0 1 1 1 1 2 2 3 3 4 5 5 6 7 7 7 8 8 9 # # # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o

If you need to mix the students around a bit, so you don't have a pair of students sharing a job from week to week, then shuffle the job rotation. Make sure that no two instances of a job are separated by a multiple of 4. Perhaps:

 job    0 # 1 1 1 1 2 5 3 4 7 2 8 5 6 7 3 7 # 8 9 # $
week 1  a b c d e f g h i j k l m n o p q r s t u v w
week 2  t u v w a b c d e f g h i j k l m n o p q r s
week 3  p q r s t u v w a b c d e f g h i j k l m n o

Answer 2

Let us first find some common-sense boundaries to possible answers:

• if there are M tasks, and kids are not allowed to repeat tasks, then there cannot be more than M assignments, because an M+1th assignment would have to repeat one among the M previous assignments. Therefore, generating M valid, non-repeating assignments is an initial upper bound.

• an initial, valid, assignment can be made by taking the list of persons (in any given order), the list of tasks (in any given order), and then simply filling tasks with persons until all are full. Note that, given a valid assignment generated by this method, all other valid assignments can be generated through a permutation of the list of persons.

• since some tasks take multiple people, those are the most difficult to fill without duplicates. For example, if there are 4 persons (a, b, c, d) and 3 tasks (x, y, z), where x takes 2 persons and y and z need only 1, there are only 2 valid assignments before someone is forced to repeat a job, instead of 3: x:a&b, y:c, z:d and x:c&d, y:a, z:b (or the equivalent x:c&d, y:b, z:a), . Therefore, a tighter bound for the maximum number of valid consecutive assignments is ceil(|P| / Tm), where Tm is the number of persons needed to staff the most person-intensive task, and P is the total amount of persons. The upper bound of M valid assignments for M tasks can only be achieved if all take exactly 1 person.

Now, for a simple algorithm:

sort all persons into a list P; random is fine       
   persons in P have an initially empty list of tasks that they have carried out
sort all tasks into a list T; random is fine
generate a valid assignment as follows:
   for each task Ti in T,
       for t = Ti (the number of people required to staff the i-th task), and t>0
           for each person Pj in P, starting from the last-assigned person,
               if Pj has never performed Ti, and has no task for the current day,
                   add Ti to Pj's tasks, and decrement t
               otherwise, skip Pj; if everybody is so skipped, then exit

At the end of the above pseudo-code, each person will have a list of tasks that they are expected to do on each consecutive day. Some may have 1 more task than others, so the number of valid assignments generated is the length of the shortest task-list. The runtime of this algorithm is clearly limited by O(vnm), where v is the number of valid consecutive assignments returned, which is itself under v*n - so for small amounts of people and tasks, this should be relatively quick.

ceil(23 / 4) = 5, so your students will have to start repeating jobs after 5 days. Implementing the above algorithm in JavaScript provides a valid (and, per the observations above, maximal) schedule:

// initialize tasks            
let tasks = new Map([
    ["Attendance", 1],
    ["Table Captain", 4],
    ["Teacher's Helper", 2],
    ["Board Eraser", 2],
    ["Light Switcher", 1],
    ["Librarian", 2],
    ["Lunch Helper", 1],
    ["Equipment Manager", 3],
    ["Trash Monitor", 2],
    ["Tech Specialist", 1],
    ["Paper Passer", 3],
    ["Pencil Sharpener", 1]
]);

// initialize people by counting total hands for all tasks
let totalPeople = 0;
for (let p of tasks.values()) totalPeople += p;
// and give each person an empty list of tasks for each assignment
let people = Array.apply(null, Array(totalPeople)).map(() => new Array());

function assign(tasks, people) {
    let moreAssignmentsMayBePossible = true;
    let assignments = 0;
    outer: while (moreAssignmentsMayBePossible) {
        let nextIndex = 0;
        for (let t of tasks) {
            let initialIndex = nextIndex;
            let [name, count] = [t[0], t[1]];
            while (count > 0) {
                if (nextIndex >= people.length) {
                    nextIndex = 0;
                }
                let candidate = people[nextIndex++];
                if (candidate.indexOf(name) == -1 && candidate.length == assignments) {
                    candidate.push(name);
                    count --;
                } else if (nextIndex == initialIndex) {
                    moreAssignmentsMayBePossible = false;
                    break outer; // no more assignments possible
                }
            }
        }
        assignments ++; // yay! finished a full assignment
    }
    // drop extra tasks from over-burdened people
    people.forEach((o) => o.length = assignments);
    return assignments;
}

assign(tasks, people);
people.forEach((o, i) => console.log(i, o.length, o.join(", ")));

Answer 3

Here is a simple greedy algorithm without any guarantees:

Create a bipartite graph where the students are nodes in one set and the task slots are nodes in the other set.

Now we create edges between students and nodes for those assignments that are viable. Initially, those are all. Once we have this graph, we can calculate a random perfect matching. For this, start with a random edge. See if none of the two incident nodes have assignments yet and fix that assignment. If one of the nodes have assignments, go to the next random edge.

This will give you a random assignment. Let's see what happens in the next week:

We need to modify the graph to exclude those edges which would produce a repetition of a task. Once we have removed those edges, we can do the same thing again and calculate a random perfect matching.

Eventually, you will arrive at a configuration where you cannot complete the matching. This can have two reasons: Either you chose the edges in a bad way or the graph does not admit a perfect matching. To remedy the first cause, you can just run the same approach multiple times with different random choices (e.g. ten times). It won't give you certainty, but it reduces the likelihood of bad choices. The second cause is a bit more tricky. This will happen after a couple of weeks when repetitions must occur because we ran out of tasks. To do this, we can add back some of the edges. Which edges to add is very variable and depends on the desired behavior of the system. I would start by adding all edges for tasks that require the most people. Among those, start with the edges for people that had the least amount of repetitions already. Once you added these edges, try to find the perfect matching again. If you are still unsuccessful, add some more edges, try again, and so on.