4
$\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$
1

1 Answer 1

3
$\begingroup$

This is the cutting stock problem with multiple stock lengths.

$\endgroup$
2
  • $\begingroup$ Thank you, this is really helpful! The only difference I see is that the problem you mention aims to minimize the total "waste", while in my case I aim to minimize the total number of "pieces of stock" used, and then, among the possible solutions with the minimum number of "pieces", I choose the one with the minimum total "waste". So the two problems are not completely equivalent, do you agree? $\endgroup$
    – RR_28023
    Commented Apr 7, 2021 at 15:48
  • 1
    $\begingroup$ There are many variants of this problem. In the classical version with one stock length, minimizing waste and minimizing pieces of stock are equivalent. For multiple stock lengths, one option is to minimize pieces of stock as a primary objective and minimize waste as a secondary objective. $\endgroup$
    – RobPratt
    Commented Apr 7, 2021 at 16:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .