title: Algorithm for fairly assigning tasks to workers based on skills
body: <p>(Before anyone asks, this is not homework.)</p>
  
  <p>I have a set of workers with interests, i.e.:</p>
  
  <ul>
  <li><p>Bob: Java, XML, Ruby</p></li>
  <li><p>Susan: Java, HTML, Python</p></li>
  <li><p>Fred: Python, Ruby</p></li>
  <li><p>Sam: Java, Ruby</p></li>
  <li><p>etc.</p></li>
  </ul>
  
  <p>(There are actually somewhere in the range of 10-25 "interests" for each worker, and I have around 40-50 workers)</p>
  
  <p>At the same time, I have a very large set of tasks that need to be distributed among the workers. Each task has to be assigned to <em>at least</em> 3 workers, and the workers must match at least one of the tasks' interests:</p>
  
  <p>Task 1: Ruby, XML
  Task 2: XHTML, Python</p>
  
  <p>and so on. So Bob, Fred, or Sam could get Task 1; Susan or Fred could get Task 2.</p>
  
  <p>This is all stored in a database thusly:</p>
  
  <pre><code>Task
      id integer primary key
      name varchar
  
  TaskInterests
      task_id integer
      interest_id integer
  
  Workers
      id integer primary key
      name varchar
      max_assignments integer
  
  WorkerInterests
      worker_id
      interest_id
  
  Assignments
      task_id
      worker_id
      date_assigned
  </code></pre>
  
  <p>Each worker has a maximum number of assignments they will do, around 10. Some interests are more rare than others (i.e. only 1 or 2 workers have listed them as a interest), some interests are more common (i.e. half of the workers list them).</p>
  
  <p>The algorithm <em>must</em>:</p>
  
  <ul>
  <li>Assign every task to 3 workers (it is
  assumed that at least 3 of the
  workers are interested in one of the
  interests of the task).</li>
  <li>Assign every worker 1 or more tasks</li>
  </ul>
  
  <p>Ideally, the algorithm will:</p>
  
  <ul>
  <li>Assign each worker a number of tasks proportional to their maximum assignments and the total number of tasks. For example, if Susan says she will do 20 tasks and most people will only do 10 tasks and there are 50 workers and 300 tasks, she should be assigned 12 tasks (20/10*(300/50)).</li>
  <li>Assign a variety of tasks to each worker, so if Susan lists 4 interests she gets tasks that include 4 interests (rather than getting 10 tasks all with the same interest)</li>
  </ul>
  
  <p>The most difficult aspect so far has been dealing with theses issues:</p>
  
  <ul>
  <li>tasks having interests with few corresponding workers</li>
  <li>workers who have few interests, especially</li>
  <li>workers who have a few interests, for which there are relatively few tasks</li>
  </ul>