0
$\begingroup$

I’m trying to solve a problem very similar to the assignment problem, with a few twists.

The problem has a certain amount of workers, and a certain amount of tasks - workers is always >= tasks. Each agent has a cost to perform each task. The goal is to assign workers to tasks such that the total cost is minimized and so that every worker is assigned a task. However, there are far more workers than tasks, and multiple workers can be assigned to a task. A task has a “capacity” of how many people can be working on it. Thus far, what I have described can still be considered the assignment problem and the constraint of multiple workers to a task can be solved with the Hungarian Algorithm by cloning tasks to the amount of workers that can perform them at once. However, there’s one last constraint that breaks pretty much everything: workers have a type and only workers of the same type can work on the same task. Tasks do not have types, but the workers who work on them must all have the same type. I suspect this problem is NP-hard and has to be solved with probabilistic optimization algorithms.

Improve this question
$\endgroup$
4
  • $\begingroup$ I think there might be a missing piece of information. If the costs are all positive, what is the incentive to assign more than one worker to a task? Is there some time dimension that needs to be considered? Or do the costs somehow decrease when assigning multiple workers to one task? Or is there a penalty for idle workers? $\endgroup$ – mhum Jul 18 '19 at 19:09
  • 1
    $\begingroup$ @mhum all workers must be assigned to a task, so there’s incentive to match both to a task if the cost is good. $\endgroup$ – Illorum Jul 18 '19 at 19:13
  • 1
    $\begingroup$ A non-trivial example may tell more than a ton of formalization. Could you edit the question to add one or two simple non-trivial example? $\endgroup$ – John L. Jul 18 '19 at 20:46
  • $\begingroup$ I'm not sure what you mean by "probabilistic optimization algorithms", but there are usually more methods to get reasonable solutions for NP-hard problems, depending on what your time constraints allow. Using IP solvers is a common approach for NP-hard scheduling problems, for example. $\endgroup$ – Discrete lizard♦ Jul 19 '19 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.