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 and each employee can work on only one project.
I am thinking of using dynamic programming but am unable to reach a recursion which I can use to fill a table. I for a m x n matrix, where m is the projects and n are the employees. Matrix[i][j]= the amount earned by the company if project i is assigned to employee j. I am stuck on how to maximize this.
Any help will be appreciated!
This looks like an a 'assignment problem' which can formulated as a linear programming problem. Here is an example formulation:
The first part is just inventing some random data. The variable x is a binary variable which usually means we need to solve the model as a mixed integer programming model. But this assignment problem has a property in which variables are integer automatically, so we can actually solve as an LP. (I solved here as an 'RMIP' which means: drop the integrality conditions on x).
The formulation is a little bit complicated as I don't want to include x(i,k)'s in the model that are not allowed.
This is an easy LP so you should be able to solve large problems quickly.