# Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given the expertise of the worker for the job $\omega(w,j)$. The goal is to select a subset of jobs $S\subseteq J$ and assign exactly two workers to each job $j \in S$ while maximizing the total expertise.

That is, if $x_{w, j} = 1$ indicates that the worker $w$ has been assigned to job $j$, solve the following program:

$$maximize \sum_{j \in S} x_{w, j} \cdot \omega(w, j)$$ s.t. $$\sum_{j\in S} x_{w, j} \leq 1, \forall w\in W$$ $$\sum_{w\in W} x_{w, j} = 2, \forall j \in S$$ $$x_{w, j} \in \{0, 1\}$$

Edit:

It seems like my explanation is not very clear so I am adding a simple example. Consider the following graph where dotted edges have weight 0 and solid edges have weight 1. Worker $i$ has expertise $1$ in job $i$ and expertise $0$ in the other job.

The two possible solutions both have value 1: either assign both workers to job 1, or assign both workers to job 2. Observe that assigning worker 1 to job 1 and worker 2 to job 2 would result in a solution of value 2, but it is not a valid solution since a job must be assigned exactly 2 workers.

• What exactly is the question? If there is a solution to the problem? Your point is not clear. – Konstantinos Koiliaris Jul 1 '15 at 16:54
• Well for one thing this is of course a case of 0-1 Integer Programming and thus some classical algorithms and heuristics such as branch and bound + cutting planes can be applied – frogeyedpeas Jul 1 '15 at 19:35
• But none of those techniques are specific to this problem – frogeyedpeas Jul 1 '15 at 19:35
• It's a min cost flow problem, so it can be solved for instance by the network simplex method. The network is a complete bipartite graph with arcs from workers to jobs. Every worker node has supply 1 and every job node has demand 2, and the cost of arc $(w,j)$ is $-\omega(w,j)$. – Thomas Kalinowski Jul 2 '15 at 2:29
• Thanks. I've overlooked the restriction to $S$. Anyway, you get a 0-1-program by replacing the right hand side of the equality constraints by $2y_j$ with a binary $y_j$ for every $j\in J$. – Thomas Kalinowski Jul 2 '15 at 6:36