Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.
Let us explore all approaches for this problem.
Solution 1: Brute Force
We generate n! possible job assignments and for each such assignment, we compute its total cost and return the less expensive assignment. Since the solution is a permutation of the n jobs, its complexity is O(n!).
Solution 2: Hungarian Algorithm
The optimal assignment can be found using the Hungarian algorithm. The Hungarian algorithm has worst case run-time complexity of O(n^3).
Solution 3: DFS/BFS on state space tree
A state space tree is a N-ary tree with property that any path from root to leaf node holds one of many solutions to given problem. We can perform depth-first search on state space tree and but successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach. We can also perform a Breadth-first search on state space tree. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.
Solution 4: Finding Optimal Solution using Branch and Bound
The selection rule for the next node in BFS and DFS is “blind”. i.e. the selection rule does not give any preference to a node that has a very good chance of getting the search to an answer node quickly. The search for an optimal solution can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like search but with one major optimization. Instead of following FIFO order, we choose a live node with least cost. We may not get optimal solution by following node with least promising cost, but it will provide very good chance of getting the search to an answer node quickly.
There are two approaches to calculate the cost function:
- For each worker, we choose job with minimum cost from list of unassigned jobs (take minimum entry from each row).
- For each job, we choose a worker with lowest cost for that job from list of unassigned workers (take minimum entry from each column).
In this article, the first approach is followed.
Let’s take below example and try to calculate promising cost when Job 2 is assigned to worker A.
Since Job 2 is assigned to worker A (marked in green), cost becomes 2 and Job 2 and worker A becomes unavailable (marked in red).
Now we assign job 3 to worker B as it has minimum cost from list of unassigned jobs. Cost becomes 2 + 3 = 5 and Job 3 and worker B also becomes unavailable.
Finally, job 1 gets assigned to worker C as it has minimum cost among unassigned jobs and job 4 gets assigned to worker C as it is only Job left. Total cost becomes 2 + 3 + 5 + 4 = 14.
Below diagram shows complete search space diagram showing optimal solution path in green.
Complete Algorithm:
/* findMinCost uses Least() and Add() to maintain the
list of live nodes
Least() finds a live node with least cost, deletes
it from the list and returns it
Add(x) calculates cost of x and adds it to the list
of live nodes
Implements list of live nodes as a min heap */
// Search Space Tree Node
node
{
int job_number;
int worker_number;
node parent;
int cost;
}
// Input: Cost Matrix of Job Assignment problem
// Output: Optimal cost and Assignment of Jobs
algorithm findMinCost (costMatrix mat[][])
{
// Initialize list of live nodes(min-Heap)
// with root of search tree i.e. a Dummy node
while (true)
{
// Find a live node with least estimated cost
E = Least();
// The found node is deleted from the list
// of live nodes
if (E is a leaf node)
{
printSolution();
return;
}
for each child x of E
{
Add(x); // Add x to list of live nodes;
x->parent = E; // Pointer for path to root
}
}
}
[ad type=”banner”]
Below is its C++ implementation.
[pastacode lang=”cpp” manual=”%2F%2F%20Program%20to%20solve%20Job%20Assignment%20problem%0A%2F%2F%20using%20Branch%20and%20Bound%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23define%20N%204%0A%20%0A%2F%2F%20state%20space%20tree%20node%0Astruct%20Node%0A%7B%0A%20%20%20%20%2F%2F%20stores%20parent%20node%20of%20current%20node%0A%20%20%20%20%2F%2F%20helps%20in%20tracing%20path%20when%20answer%20is%20found%0A%20%20%20%20Node*%20parent%3B%0A%20%0A%20%20%20%20%2F%2F%20contains%20cost%20for%20ancestors%20nodes%0A%20%20%20%20%2F%2F%20including%20current%20node%0A%20%20%20%20int%20pathCost%3B%0A%20%0A%20%20%20%20%2F%2F%20contains%20least%20promising%20cost%0A%20%20%20%20int%20cost%3B%0A%20%0A%20%20%20%20%2F%2F%20contain%20worker%20number%0A%20%20%20%20int%20workerID%3B%0A%20%0A%20%20%20%20%2F%2F%20contains%20Job%20ID%0A%20%20%20%20int%20jobID%3B%0A%20%0A%20%20%20%20%2F%2F%20Boolean%20array%20assigned%20will%20contains%0A%20%20%20%20%2F%2F%20info%20about%20available%20jobs%0A%20%20%20%20bool%20assigned%5BN%5D%3B%0A%7D%3B%0A%20%0A%2F%2F%20Function%20to%20allocate%20a%20new%20search%20tree%20node%0A%2F%2F%20Here%20Person%20x%20is%20assigned%20to%20job%20y%0ANode*%20newNode(int%20x%2C%20int%20y%2C%20bool%20assigned%5B%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20Node*%20parent)%0A%7B%0A%20%20%20%20Node*%20node%20%3D%20new%20Node%3B%0A%20%0A%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20node-%3Eassigned%5Bj%5D%20%3D%20assigned%5Bj%5D%3B%0A%20%20%20%20node-%3Eassigned%5By%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20node-%3Eparent%20%3D%20parent%3B%0A%20%20%20%20node-%3EworkerID%20%3D%20x%3B%0A%20%20%20%20node-%3EjobID%20%3D%20y%3B%0A%20%0A%20%20%20%20return%20node%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20calculate%20the%20least%20promising%20cost%0A%2F%2F%20of%20node%20after%20worker%20x%20is%20assigned%20to%20job%20y.%0Aint%20calculateCost(int%20costMatrix%5BN%5D%5BN%5D%2C%20int%20x%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20y%2C%20bool%20assigned%5B%5D)%0A%7B%0A%20%20%20%20int%20cost%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20to%20store%20unavailable%20jobs%0A%20%20%20%20bool%20available%5BN%5D%20%3D%20%7Btrue%7D%3B%0A%20%0A%20%20%20%20%2F%2F%20start%20from%20next%20worker%0A%20%20%20%20for%20(int%20i%20%3D%20x%20%2B%201%3B%20i%20%3C%20N%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20min%20%3D%20INT_MAX%2C%20minIndex%20%3D%20-1%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20do%20for%20each%20job%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20if%20job%20is%20unassigned%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(!assigned%5Bj%5D%20%26%26%20available%5Bj%5D%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20costMatrix%5Bi%5D%5Bj%5D%20%3C%20min)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20store%20job%20number%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20minIndex%20%3D%20j%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20store%20cost%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min%20%3D%20costMatrix%5Bi%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20add%20cost%20of%20next%20worker%0A%20%20%20%20%20%20%20%20cost%20%2B%3D%20min%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20job%20becomes%20unavailable%0A%20%20%20%20%20%20%20%20available%5BminIndex%5D%20%3D%20false%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20cost%3B%0A%7D%0A%20%0A%2F%2F%20Comparison%20object%20to%20be%20used%20to%20order%20the%20heap%0Astruct%20comp%0A%7B%0A%20%20%20%20bool%20operator()(const%20Node*%20lhs%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20const%20Node*%20rhs)%20const%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20return%20lhs-%3Ecost%20%3E%20rhs-%3Ecost%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%20%0A%2F%2F%20print%20Assignments%0Avoid%20printAssignments(Node%20*min)%0A%7B%0A%20%20%20%20if(min-%3Eparent%3D%3DNULL)%0A%20%20%20%20%20%20%20%20return%3B%0A%20%0A%20%20%20%20printAssignments(min-%3Eparent)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Assign%20Worker%20%22%20%3C%3C%20char(min-%3EworkerID%20%2B%20’A’)%0A%20%20%20%20%20%20%20%20%20%3C%3C%20%22%20to%20Job%20%22%20%3C%3C%20min-%3EjobID%20%3C%3C%20endl%3B%0A%20%0A%7D%0A%20%0A%2F%2F%20Finds%20minimum%20cost%20using%20Branch%20and%20Bound.%0Aint%20findMinCost(int%20costMatrix%5BN%5D%5BN%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20priority%20queue%20to%20store%20live%20nodes%20of%0A%20%20%20%20%2F%2F%20search%20tree%3B%0A%20%20%20%20priority_queue%3CNode*%2C%20std%3A%3Avector%3CNode*%3E%2C%20comp%3E%20pq%3B%0A%20%0A%20%20%20%20%2F%2F%20initailize%20heap%20to%20dummy%20node%20with%20cost%200%0A%20%20%20%20bool%20assigned%5BN%5D%20%3D%20%7Bfalse%7D%3B%0A%20%20%20%20Node*%20root%20%3D%20newNode(-1%2C%20-1%2C%20assigned%2C%20NULL)%3B%0A%20%20%20%20root-%3EpathCost%20%3D%20root-%3Ecost%20%3D%200%3B%0A%20%20%20%20root-%3EworkerID%20%3D%20-1%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20dummy%20node%20to%20list%20of%20live%20nodes%3B%0A%20%20%20%20pq.push(root)%3B%0A%20%0A%20%20%20%20%2F%2F%20Finds%20a%20live%20node%20with%20least%20cost%2C%0A%20%20%20%20%2F%2F%20add%20its%20childrens%20to%20list%20of%20live%20nodes%20and%0A%20%20%20%20%2F%2F%20finally%20deletes%20it%20from%20the%20list.%0A%20%20%20%20while%20(!pq.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%20Find%20a%20live%20node%20with%20least%20estimated%20cost%0A%20%20%20%20%20%20Node*%20min%20%3D%20pq.top()%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20The%20found%20node%20is%20deleted%20from%20the%20list%20of%0A%20%20%20%20%20%20%2F%2F%20live%20nodes%0A%20%20%20%20%20%20pq.pop()%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20i%20stores%20next%20worker%0A%20%20%20%20%20%20int%20i%20%3D%20min-%3EworkerID%20%2B%201%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20if%20all%20workers%20are%20assigned%20a%20job%0A%20%20%20%20%20%20if%20(i%20%3D%3D%20N)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20printAssignments(min)%3B%0A%20%20%20%20%20%20%20%20%20%20return%20min-%3Ecost%3B%0A%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%2F%2F%20do%20for%20each%20job%0A%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20unassigned%0A%20%20%20%20%20%20%20%20if%20(!min-%3Eassigned%5Bj%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20create%20a%20new%20tree%20node%0A%20%20%20%20%20%20%20%20%20%20Node*%20child%20%3D%20newNode(i%2C%20j%2C%20min-%3Eassigned%2C%20min)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20cost%20for%20ancestors%20nodes%20including%20current%20node%0A%20%20%20%20%20%20%20%20%20%20child-%3EpathCost%20%3D%20min-%3EpathCost%20%2B%20costMatrix%5Bi%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20calculate%20its%20lower%20bound%0A%20%20%20%20%20%20%20%20%20%20child-%3Ecost%20%3D%20child-%3EpathCost%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20calculateCost(costMatrix%2C%20i%2C%20j%2C%20child-%3Eassigned)%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%2F%2F%20Add%20child%20to%20list%20of%20live%20nodes%3B%0A%20%20%20%20%20%20%20%20%20%20pq.push(child)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Driver%20code%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20x-cordinate%20represents%20a%20Worker%0A%20%20%20%20%2F%2F%20y-cordinate%20represents%20a%20Job%0A%20%20%20%20int%20costMatrix%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B9%2C%202%2C%207%2C%208%7D%2C%0A%20%20%20%20%20%20%20%20%7B6%2C%204%2C%203%2C%207%7D%2C%0A%20%20%20%20%20%20%20%20%7B5%2C%208%2C%201%2C%208%7D%2C%0A%20%20%20%20%20%20%20%20%7B7%2C%206%2C%209%2C%204%7D%0A%20%20%20%20%7D%3B%0A%20%0A%20%0A%20%20%20%20%2F*%20int%20costMatrix%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B82%2C%2083%2C%2069%2C%2092%7D%2C%0A%20%20%20%20%20%20%20%20%7B77%2C%2037%2C%2049%2C%2092%7D%2C%0A%20%20%20%20%20%20%20%20%7B11%2C%2069%2C%20%205%2C%2086%7D%2C%0A%20%20%20%20%20%20%20%20%7B%208%2C%20%209%2C%2098%2C%2023%7D%0A%20%20%20%20%7D%3B%0A%20%20%20%20*%2F%0A%20%0A%20%20%20%20%2F*%20int%20costMatrix%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B2500%2C%204000%2C%203500%7D%2C%0A%20%20%20%20%20%20%20%20%7B4000%2C%206000%2C%203500%7D%2C%0A%20%20%20%20%20%20%20%20%7B2000%2C%204000%2C%202500%7D%0A%20%20%20%20%7D%3B*%2F%0A%20%0A%20%20%20%20%2F*int%20costMatrix%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B90%2C%2075%2C%2075%2C%2080%7D%2C%0A%20%20%20%20%20%20%20%20%7B30%2C%2085%2C%2055%2C%2065%7D%2C%0A%20%20%20%20%20%20%20%20%7B125%2C%2095%2C%2090%2C%20105%7D%2C%0A%20%20%20%20%20%20%20%20%7B45%2C%20110%2C%2095%2C%20115%7D%0A%20%20%20%20%7D%3B*%2F%0A%20%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnOptimal%20Cost%20is%20%22%0A%20%20%20%20%20%20%20%20%3C%3C%20findMinCost(costMatrix)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D%0ARun%20on%20IDE%0A” message=”” highlight=”” provider=”manual”/]Output :
Assign Worker A to Job 1 Assign Worker B to Job 0 Assign Worker C to Job 2 Assign Worker D to Job 3 Optimal Cost is 13