Maximum profit by optimizing assignment

Question

So a company has n available projects and k employees on the bench. Each project has a "number of hours" associated with it. Each employee has an hourly rate that the parent company gets paid gets paid if he is on a project. Not all employees can be assigned to any project i.e. each employee has a subset of the n projects he can work on. I want to assign the employees to projects so that I can maximize what the company makes from the assignment. Each project can be assigned to only one employee.

I am thinking of using dynamic programming but am unable to reach a recursion which I can use to fill a table. I am thinking along the lines of: Max_profit= max(For each employee -> {assign him to each of the projects on his available list and recurse with the remaining projects on the remaining employees or do not assign him to any project and recurse}.

Any help will be appreciated!

Answer 1

I would use the Hungarian algorithm. For the projects that cannot be assigned to certain employees, just give these project/employee pairs a huge cost value in your matrix.

Answer 2

Create the bipartite graph $G=(V_1\cup V_2,E)$, where

• $V_1$ is the set of $k$ employees;
• $V_2$ is the set of $n$ tasks;
• $E$ is the set of edges between vertices of $V_1$ and $V_2$; specifically an edge exists between $u\in V_1$ and $v\in V_2$ if employee $u$ can work on project $v$. On each of these edges $(u,v)$, add the total profit obtained by the company if employee $u$ is assigned project $v$, multiplied by $-1$.

Maximizing the total profit is now a minimum cost flow problem on this graph, for which many efficient algorithms exist. See for example this book, it is an excellent reference for network flow problems.