1
$\begingroup$

The assignment problem is defined as:

Let there be n agents and m tasks. Any agent can be assigned to perform any task, incurring some costs that may vary depending on the agent-task assignment. We can assign at most one task for one person and at most one person for one task in such a way that the total cost of the assignment is maximized.

The Hungarian algorithm can solve this problem.

Question:

For example, I have a cost matrix as below:

     T1   T2   T3
P1   2    2    2
P2   3    1    4

$T_{i}$ is the $i_{th}$ task, $P_{i}$ is the $i_{th}$ person.

The number in the row $P_{i}$ and col $T_{i}$ is the cost when assigning task $T_{i}$ to person $P_{i}$.

One solution for the above problem is: $P_1 - T1, P_2 - T_3$, the max cost is 2 + 4 = 6.

I want to add some constraints like:

  • Some people can do a task together (e.g: $P_1$ and $P_2$ can do task $T1$ together with a cost of 10)

  • Some people can do some tasks together (e.g: $P_1$ and $P_2$ can do task $T1$ and $T2$ together with a cost of 10)

  • A person can do some tasks (e.g: $P_1$ can do task $T1$ and $T2$ consequently with a cost of 10)

So, the new solution for the above problem is: $P1,P2-T1,T2$, the max cost is 10

How to approach solving this problem?

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to ORSE. Would you please, is it a homework training? $\endgroup$
    – A.Omidi
    May 16 at 7:37
  • 3
    $\begingroup$ The problem specifies that you are maximizing cost. Is this a government operation? $\endgroup$
    – prubin
    May 16 at 15:02
  • $\begingroup$ Actually, it will be minimized the cost but I have negated the cost, so it becomes maximized. $\endgroup$
    – Linh OR
    May 17 at 1:48

2 Answers 2

3
$\begingroup$

You can create additional "group agents" that represent combinations of actual agents (for instance, $P_{17}$ might be the pairing of $P_1$ and $P_2$) and/or additional "combo tasks" that are combinations of original tasks (for instance, $T_{9}$ might be $T_1$ and $T_3$ done together). You then assign "agents" to "tasks" using binary variables, and add constraints that preclude assigning a "group agent" to a task and also assigning one of the group's members (or another group sharing a member) to a different task, as well as constraints preventing an individual task and a "combo task" including that task (or two "combo tasks" that intersect) from being assigned simultaneously. This can be modeled as a binary integer program and solved by branch-and-bound/branch-and-cut.

$\endgroup$
2
$\begingroup$

This sounds like a special case of the parallel assignment problem in which the preemption (this is a standard notation in the scheduling theory) would be allowed. I am not aware of how this problem can still be solved by the Hungarian algorithm in an efficient way, but there are some algorithms to tackle such a problem, like $\text{LRPT}$, Longest Remaining Processing Time first. Also, another approach to solving this problem is Linear programming.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.