I have a bipartite graph $G = (G_1 \cup G_2, E)$ where we suppose $|G_1| \le |G_2|$.
Each vertex $V \in G_1$ represents a worker. A worker $V$ has two associated values:
- a workgroup index $g(V) \in \mathbb{N}$;
- an employment level $e(V) \in \mathbb{N}$.
Any two workers are necessarily differentiated on at least one of the two values, i.e. $\forall V, V' \in G_1 : g(V) = g(V') \wedge e(V) = e(V') \Rightarrow V = V'$.
Similarly, a vertex $W$ from $G_2$ represents a machine, which also has two associated values:
- a location $l(W) \in \mathbb{N}$;
- a machine type $t(W) \in \mathbb{N}$.
As with the workers, two machines are necessarily differentiated on at least one of the two values, i.e. $\forall W, W' \in G_2 : l(W) = l(W') \wedge t(W) = t(W') \Rightarrow W = W'$.
We are also given a weight function $w : G_1 \times G_2 \mapsto \mathbb{N}$ such that $w(V,W)$ of represents the profit of having the worker $V$ working on the machine $W$.
The problem is to find a maximum weight matching between the vertexes of $G_1$ and those of $G_2$ (each worker being assigned to one machine maximum), but with the following two additional constraints :
- Workers from a given workgroup must be assigned on machines that are at a same location $L$, and no worker from another workgroup can be assigned to a machine at the same location $L$. In other words, having an edge between $V$ and $W$ in the solution implies that no edge between $V'$ and $W'$, where $g(V) = g(V') \wedge l(W) \neq l(W')$ or where $l(W) = l(W') \wedge g(V) \neq g(V')$, is also part of the solution.
- Similarly, all workers having the same employment level should be assigned to machines that are of the same type; no worker of a different employment level can be assigned to a machine of that type.
Another way of describing the problem is to consider that there are two interleaved matchings to be found : one among the workgroups and the locations, and one among the employment levels and the machine types, such that the induced selected edges in $G$ are of maximal weight.
I am having trouble identifying to which variant of the assignment problem this could refer to. In particular, I am trying to achieve a complexity result for this problem. I have tried to reduce several NP-complete problems to this one, but my attempts thus far have been unsuccessful.
When formalizing the problem as an integer linear program, I get an extension of the classical assignment problem in linear form, where additional constraints appear to represent the workers from different workgroups/levels having to be paired with machines from different locations/types. The resulting constraint matrix is not totally unimodular so that I cannot directly conclude that the problem is solvable in polynomial time. Is it a special case of integer programming that is tractable, or should it be assimilated to general integer programming (known to be NP-complete)?
Does someone have an idea or a lead that could help? I would be extremely grateful. :-)