2
$\begingroup$

Is there an algorithm for the following variant of the assignment problem:

Suppose we have $n$ workers $A_i$ and $m$ tasks and each worker $A_i$ has to do exactly $t_i$ tasks. (The numbers are chosen such that $m= \sum_{i=1}^n t_i$.) For any $i$ let $C_i$ be the sum of the costs of worker $A_i$. I am searching for an assignment such that $\max_i C_i$ is minimal.

I have found this variant, but this deals only with the maximal cost of one task, not with the sum of the tasks for one worker.

$\endgroup$
1
$\begingroup$

I would solve this problem via integer programming. Let $x_{ij}$ be decision variable for the worker $A_i$ do the task $j$ and $c_{ij}$ be the cost of worker $A_i$ do the task $j$. We have $C_i = \sum\limits_{j=1}^mc_{ij}x_{ij}$. We need to solve the following IP: $\min z$ subject to $\sum\limits_{j=1}^mx_{ij} = t_i$ and $\sum\limits_{j=1}^mc_{ij}x_{ij} \leq z$ for all $i=1,\ldots,n$, and $x_{ij}\in \{0,1\}$.

$\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.