1
$\begingroup$

I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next paragraph. My question is whether such problem has a an equivalent problem with a "famous" name (similarly to what happens with problems like the Knapsack problem or the Job Shop Scheduling problem), since that would make my search much easier.

The problem in question is: given n tasks T1, T2, ..., Tn of varying cost $c_{i}$, and m nodes N1, ..., Nm with varying capacity $r_{i}$, what is the task allocation that minimizes the number of used nodes as priority 1, and the total quantity of free resources in the used nodes as priority 2.

So for example, if I have tasks {T1, T2} with costs {3, 7}, and nodes {N1, N2, N3} with capacity {5, 11, 12}. The optimal alocation would be assigning T1 and T2 to N2, since it would require only one node, and the number of free resources is $11 - 7 - 3 = 1$.

Any tips on what sort of terminology I could use on my search are also welcome! Same applies to suggestions on similar "famous" problems that, even if not equivalent, could be interesting to look at (as per my comments above, I am already familiar with the Knapsack and the JSS problems).

Thank you very much!

$\endgroup$
2
  • $\begingroup$ If there is only one priority (number of used nodes), then it is bin packing. $\endgroup$ – Chao Xu Apr 7 at 5:50
  • $\begingroup$ A good search term should be "variable sized bin packing". $\endgroup$ – Gamow Apr 7 at 9:35

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.