Algorithm: Distribute n tasks to k >n people, each of whom can perform a subset of these tasks

Question

I'm trying to find an efficient solution for the following problem:

Problem: Assume I have some tasks (A,A,B,B,C) and I have some people who can perform one or more of these tasks:

• person1: A,B (person 1 could do task A or task B)
• person2: A,C
• person3: A
• person4: B,C
• person5: A,B

Is it possible to give away all of my tasks to these persons? One person can only do one task.

There could be multiple solutions but I'm only interested in knowing if there is a solution.

My first attempt at solving this efficiently was:

• if a person can do only 1 task, assign that task to that person
• If a task needs to be done n times, and there are n people who can do this task, assign this task to those n people.

This is good enough for solving the above problem.

• 2 people can do B, B needs to be done twice.
  • tasks left: A,A,C
  • persons left: [A,C],[A],[B,C]
• 2 people can do A.
  • tasks left: C
  • persons left: [B,C]

But it isn't enough to solve more complex problems like: jobs: IGGGFFDDCCBBB persons: ABCDEFG CEI BEI CEFGI CEGI ADGI CEGI CI ADG BEI DI BCDEFI ABDF ABEFG BCEGI ACDI BD ABE BCDEFGI

Is there an efficient way of solving this problem? I can obviously solve this with a depth-first search algorithm but I'm wondering if I can solve this problem in polynomial time? I can't help but believe this is a well-known problem, but I have been unable to find it on google.

Thank you for reading :)

Answer 1

One way to efficiently solve this is to formulate it as a maximum flow problem.

Add edges between people and the tasks they can do (capacity 1).

Also add edges between a start and each person (capacity 1)

And an edge between a task and the destination (capacity = number of times that task needs to be done).

Example Python code using NetworkX:

import networkx as nx
from collections import Counter

jobs = 'IGGGFFDDCCBBB'
people = 'ABCDEFG CEI BEI CEFGI CEGI ADGI CEGI CI ADG BEI DI BCDEFI ABDF ABEFG BCEGI ACDI BD ABE BCDEFGI'

G=nx.DiGraph()
for person,tasks in enumerate(people.split()):
    P = 'person'+str(person)
    G.add_edge('start',P,capacity=1.0) # One person can do one thing
    for task in tasks:
        G.add_edge(P,'task'+task,capacity=1.0) # This person can do this task

C = Counter(jobs)
for task,count in C.items():
    G.add_edge('task'+task,'end',capacity=count) # Task appears count times in our job list

print nx.max_flow(G,'start','end') >= len(jobs)

Answer 2

Yes, there is an efficient algorithm for this. This is an instance of the maximum bipartite matching problem. What you do is you create a bipartite graphs where the nodes are people and tasks, and there is an edge connecting each person with each task they are able to perform. An assignment of people to tasks will correspond to a matching of this graph.

The algorithm for this isn't completely trivial, but it can be performed efficiently, for example: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/matching.pdf