NP completeness of a variant of assignment problem

159 Views Asked by At

I have the following variant of assignment problem:

Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ has a load of $D_j$ and the goal is to find if there exists a satisfying assignment where each job is assigned to one machine and no machine's load exceeds its capacity.

Hence the input is: $m$ positive numbers $C_1,...,C_m$, $n$ positive numbers $D_1,...,D_n$ and the knowledge of whether machine $i$ is capable of job $j$ for all $i,j$.

This variant is a bit different from original assignment problem as now each machine is only capable of a certain subset of jobs. I personally believe it is NP complete, however, I am not able to prove it...