1
$\begingroup$

I have an assignment problem where each task $t_i$ requires $n_i$ agents to complete it (there are many more agents available then there are tasks for them to complete, even with multiple agents required per task). What optimization technique should I use to find the solution? Is there a non brute force solution to this?

$\endgroup$
  • 1
    $\begingroup$ Do you know about integer programming? You can kind of look at this as an instance of the jobshop scheduling problem. for solutions, Google's ortools are pretty good. developers.google.com/optimization $\endgroup$ – EDZ Mar 22 '18 at 20:47
  • $\begingroup$ Ah I should have specified that the time it takes to complete a task isn't necessarily an integer. $\endgroup$ – Andrew Mar 22 '18 at 20:52
  • $\begingroup$ @Andrew What are you trying to minimize here, exactly? The total amount of time that agents spend on tasks? Or the amount of time it takes to finish all tasks (assuming that all tasks are started at the same time)? $\endgroup$ – Math1000 Mar 22 '18 at 20:54
  • $\begingroup$ All tasks start simultaneously, and agents cannot be reassigned to other tasks once things have started. If you have multiple agents on a task, the cost taken to complete the task $t_i$ is a sum of the cost for each agent for this particular task, $\sum^{n_i}_{j}C(a_j, t_i)$. So we would want to minimize the sum of these sums. $\endgroup$ – Andrew Mar 22 '18 at 21:08
  • 1
    $\begingroup$ @Andrew It doesn't matter if the time isn't integer you can still solve with an IP. What makes it integer is that you can only assign tasks discretely to agents. If you can assign fractions of tasks to agents / interrupt then it may make the problem easier and you can solve with Simplex. If only some can be interrupted, then you can formulate an MIP (mixed integer program). There's also a heuristic for this called Johnson's algorithm which is decent if your problem can be reduced to the jobshop problem. can $\endgroup$ – EDZ Mar 22 '18 at 21:09
2
$\begingroup$

Let $T$ be the set of tasks, $A$ the set of agents, $n_t$ the number of agents required for task $t$, and $c_{a,t}$ the cost of assigning agent $a$ to task $t$. Define $$ x_{a,t} = \begin{cases} 1,& \text{if agent $a$ is assigned to task $t$}\\ 0,& \text{otherwise}. \end{cases} $$ Then we can model this problem as the following integer program: \begin{align} \min\quad &\sum_{a\in A}c_{a,t}x_{a,t}\\ \mathrm{s.t.}\quad &\sum_{a\in A} x_{a,t} = n_t,\quad t\in T\\ &\sum_{t\in T} x_{a,t} \leqslant 1,\quad a\in A\\ &x_{a,t}\in\{0,1\}. \end{align}

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