Optimal assignment of jobs that can be solved by one strong worker or multiple weak workers

Question

I'm looking for an effective way of achieving optimal job/worker assignation. I'd use Hungarian Algorithm but there is a catch: a worker can be assigned to only one job at a time and each job has a rating and each worker has his own rating. A job rated 4 can be solved by either a worker with rating 4 or by multiple workers with their combined ratings equal to the rating of the job, e.g. 2+2 or 3+1 or 2+1+1 or 1+1+1+1. A job rated 2 can be solved by two workers rated 1 or one worker rated 2. I'd like to prefer one-to-one assignation whenever possible.

Is there any known algorithm or any simple way to achieve optimal assignation in this case?

Answer 1

I think we could also make an argument that the problem is at least as hard as NP-Complete, if we consider Subset Sum.

Transform it into this decision problem:

Given one job with rating N whose value is in the set of all real numbers, and M workers with ratings R_i for i in [0, M), where each rating is in the set of all real numbers, is there a subset of workers whose rating adds up to N?

In our case, we may be restricting the problem to positive integers, but the decision problem remains, and is in fact much harder because we have many jobs as well, and we want to maximize the number of jobs completed.

Answer 2

Your problem is clearly at least as hard as the Partition Problem, even just to know if a feasible solution exists. To show this, let's have a partition instance. It can be easily transformed into your problem by creating two jobs and as many workers as the number of elements in the partition problem. Each work has a rating equal to the value of the corresponding element in the partition problem. Your problem has a solution if and only if the Partition problem has a solution, hence proving that your problem is NP-hard.