I am trying to solve an assignment problem with $N$ agents and $M$ tasks. There are more agents than tasks and in each situation, $N/M$ agents must be assigned to a one task. In other words, each task will be assigned the same number of agents and there are exactly as many agents as are needed to service the tasks at hand. Hence: $$\sum_{n=1}^N{x_{n,m}} = N , \text{where } m=1\ldots M$$ $$\sum_{m=1}^M{x_{n,m}} = 1 , \text{where } n=1\ldots N$$

All tasks are equally 'costly', hence it doesn't matter where the agents are assigned to. What matters, however, it that the agents get along optimally well. So the goal is to assign $N/M$ agents to a task that work best together. To quantify, how well each agent gets along with the others, there is a compatibility matrix $C(i,j)$ of size $N \times N$. When agent $i$ gets along with agent $j$ in a perfect manner: $$C(i,j)=0$$ The worse they get along, the larger $C(i,j)$ becomes.

What is the name for this formal problem and/or how can I solve this?


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.