Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly escalates in time :(

Formally we have $N$ wooden planks each $L_1, \dots, L_N$ cm long. And we want to have $M$ pieces, $l_1, l_2, \dots, l_M$ cm long. How to minimize the waste?

  • $\begingroup$ Is your problem only for 2 planks 1 meter each, and your pieces are always 4 with 60, 30, 50, and 20 cm? What is input? What varies? What is constant? For this specific scenario is not 60 + 30 and 50 + 20 a solution? $\endgroup$ – fade2black Jul 28 '17 at 9:27
  • 1
    $\begingroup$ Can you formulate your problem more generally and formally? Assume I know nothing about woodworking. $\endgroup$ – Yuval Filmus Jul 28 '17 at 9:41
  • $\begingroup$ The number of planks can vary as well as different lengths and different amount and sizes of sawed pieces. So all variables varies. $\endgroup$ – Viktor Eriksson Jul 28 '17 at 9:42
  • $\begingroup$ Please check if I guessed correctly. $\endgroup$ – fade2black Jul 28 '17 at 9:50
  • $\begingroup$ Also, it would be helpful if you added a specific example with the corresponding optimal solution. $\endgroup$ – fade2black Jul 28 '17 at 9:55

This problem seems to be NP-hard. Please check Cutting stock problem. Nevertheless, you could attack it using LP or other approximation methods.

  • $\begingroup$ Having some problems mapping my problem to the definition of cutting stock problem. Would my problem one dimensional ? $\endgroup$ – Viktor Eriksson Aug 1 '17 at 18:14

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.