Algorithm: optimally distribute N people among M tasks given P preferences

Question

Example: 10 candidates each give 2 preferences (the first being more preferred than the second) for 3 available jobs, and their boss must then optimally allocate (and evenly distribute) them evenly based on their preferences. Obviously, unwanted jobs will require some random draw.

How would I write an algorithm that calculates this optimal allocation automatically?

I looked around and found bipartite graphs which might give me some clues, however I am having trouble wrapping my head around it!

For the "luck" aspect of the game, I already implemented a simple Fisher Yates Shuffle.

Preference weight: If there are 2 preferences, when assigned to a worker, obtaining a first choice weighs +2, a second choice +1, an unwanted choice -1 (for example). The "optimality" goal is to maximize the aggregate preferences.

Answer 1

Your question is quite challenging, but i found a working (maybe not the most performant) solution. My Example is written in PHP, but you should be able to adapt it. I'll try to explain the "thoughts" behind the code.

Note: It seems like you added the "10 persons, 3 Jobs" constraint later - or i simple did overread it. However, my code should give you an example that you might be able to adapt to that constraint. My Code currently is assuming that there are n jobs for n persons. (The most easiest way of adapting it to the 10/3 criteria, would be to split up the 3 Jobs into 10 equal units of work, when assuming 10 workers!)

First, lets create some basic architecture stuff. We need person, job and obviously a matrix, representing the satisfaction of a person towards a job. The following snipped does exactly that:

<?php
class Person{
  var $name;
  var $prim;
  var $sec;

  function __construct($name, $prim, $sec){
    $this->name = $name;
    $this->prim = $prim;
    $this->sec = $sec;
  }

  function likes($job){
    if ($job->type == $this->prim) return 2;
    if ($job->type == $this->sec) return 1;
    else return -1;
  }
}

class Job{
  var $name;
  var $type;

  function __construct($name, $type){
    $this->name = $name;
    $this->type = $type;
  }
}


$persons = array(
  "Max" => new Person("Max", "programing", "testing"),
  "Peter" => new Person("Peter", "testing", "docu"),
  "Sam" => new Person("Sam", "designing", "testing")
);

$jobs = array(
  "New Classes" => new Job("New Classes", "programing"),
  "Theme change" => new Job("Theme change", "designing"),
  "Test Controller" => new Job("Test Controller", "testing")
);


// debug: draw it: 
echo "<h2>Happines with Jobs</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";       
foreach ($jobs AS $job){
  $j=0;
  foreach ($persons as $person){
    if ($p++==0){
      echo "<tr><td></td>";
      foreach ($persons as $per) {
        echo "<td>".$per->name."</td>";
      }                             
      echo "</tr>";
    }


    if ($j++==0){
      echo "<td>".$job->name."</td>";
    }

    echo "<td>".$person->likes($job)."</td>";
  }
  echo "</tr>";
}
echo "</table>";

This will give you a table like this:

Second, we need to create ALL permutations of jobs and persons. (actually we don't need to, but doing so, will show you the reason, why we don't need to!)

To create all permutations, we are using just the name of a person or job. (we can resolve the name back to the actual object later)

//build up all permutations
$personNames = array();
foreach ($persons AS $person){
  $personNames[] = $person->name;
}

$jobNames = array();
foreach ($jobs AS $job){
  $jobNames[] = $job->name;
}              

$personsPerms = array();
pc_permute($personNames,$personsPerms);

$jobsPerms = array();
pc_permute($jobNames,$jobsPerms);     

function pc_permute($items, &$result, $perms = array( )) {
    if (empty($items)) { 
      $result[] = join('/', $perms);
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems,$result, $newperms);
         }
    }
}

Now, we have 2 Arrays: All job permutations and all person permutations. For the Example given above, the arrays will look like this (3 Elements each, makes 3*2*1=6 Permutations per Array):

Array
(
    [0] => Max/Peter/Sam
    [1] => Peter/Max/Sam
    [2] => Max/Sam/Peter
    [3] => Sam/Max/Peter
    [4] => Peter/Sam/Max
    [5] => Sam/Peter/Max
)
Array
(
    [0] => New Classes/Theme change/Test Controller
    [1] => Theme change/New Classes/Test Controller
    [2] => New Classes/Test Controller/Theme change
    [3] => Test Controller/New Classes/Theme change
    [4] => Theme change/Test Controller/New Classes
    [5] => Test Controller/Theme change/New Classes
)

Now, We can create a nXn Table, containing ALL Values of the overall satisfaction for ALL possible job allocations:

// debug: draw it:            
echo "<h2>Total Happines of Combination (full join)</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";
$row = 0;
$calculated = array();       
foreach ($jobsPerms AS $jobComb){
  $j=0;
  $jobs_t = explode("/", $jobComb);
  foreach ($personsPerms as $personComb){

    if ($p++==0){
      echo "<tr><td></td>";
      foreach ($personsPerms as $n) {
        echo "<td>".$n."</td>";
      }                             
      echo "</tr>";
    }


    if ($j++==0){
      echo "<td>".$jobComb."</td>";
    }

    $persons_t = explode("/", $personComb);
    $h = 0;


    echo "<td>";
    for ($i=0; $i< count($persons_t); $i++){      
      $h += $persons[$persons_t[$i]]->likes($jobs[$jobs_t[$i]]);
    }
    echo $h;
    echo "</td>";

  }
  $col=0;
  $row++;
  echo "</tr>";
}
echo "</table>";

Lets call this matrix "M"

This Matrix contains a "lot" of double combinations: (a/b) TO (1/2) is equal to (b/a) to (2/1) etc...

After all: We simple can ignore:

• Either Each row > 1
• OR Each column > 1

Ignoring all Columns > 1:

echo "<h2>Total Happines of Combination (ignoring columns)</h2> ";
echo "<table border=1>";
$p=0;
echo "<tr>";
$row = 0;
$calculated = array();       
foreach ($jobsPerms AS $jobComb){
  $j=0;
  $jobs_t = explode("/", $jobComb);
  $col = 0;
  $personComb = $personsPerms[0];

  if ($p++==0){
    echo "<tr><td></td>";
    echo "<td>".$personsPerms[0]."</td>";        
    echo "</tr>";
  }


  if ($j++==0){
    echo "<td>".$jobComb."</td>";
  }

  $persons_t = explode("/", $personComb);
  $h = 0;


  echo "<td>";
  for ($i=0; $i< count($persons_t); $i++){      
    $h += $persons[$persons_t[$i]]->likes($jobs[$jobs_t[$i]]);
  }
  echo $h;
  echo "</td>";

  $col=0;
  $row++;
  echo "</tr>";
}
echo "</table>";

Output:

And there you go! In this Example (one of) the most satisfying Solution would be:

• Max -> New Classes (+2)
• Peter -> Test Controller (+2)
• Sam -> Theme Change (+2)

-> Happiness: 6.

There are other, equal distributions as well.

Example: 6 persons / 6 jobs:

$persons = array(
  "Max" => new Person("Max", "programing", "testing"),
  "Peter" => new Person("Peter", "testing", "docu"),
  "Sam" => new Person("Sam", "designing", "testing"),
  "Jeff" => new Person("Jeff", "docu", "programing"),
  "Fred" => new Person("Fred", "programing", "designing"),
  "Daniel" => new Person("Daniel", "designing", "docu") 
);

$jobs = array(
  "New Classes" => new Job("New Classes", "programing"),
  "Theme change" => new Job("Theme change", "designing"),
  "Test Controller" => new Job("Test Controller", "testing"),
  "Create Manual" => new Job("Create Manual", "docu"),
  "Program more!" => new Job("Program more!", "programing"),
  "Style the frontend" => new Job("Style the frontend", "designing")
);

results in (Persons: Max / Peter / Sam / Jeff / Fred / Daniel)