How to calculate the most efficient cut for wooden boards

Question

I need to know what is the most efficient cut (less remanent and less wooden boards possible) to get the following pieces:

80 pieces sized 50cm x 60cm

80 pieces sized 50cm x 70cm

80 pieces sized 60cm x 70cm

The wooden boards come with a size of 122cm x 244cm.

I know that if i think of total area, i could cover the total area of the pieces with 29 wooden boards, but since there are always remanents, i can´t rely that i will be able to make it with only 29 boards, and if i can, how should i cut the boards in order to achieve that.

Answer 1

Using PowerPoint as graphics tool, I manually identified eleven different configurations to place the three different types of pieces on the wooden boards.

To find the best mix of cutting configurations, I wrote a linear program model for the GLPK solver:

var x1, >= 0, integer;
var x2, >= 0, integer;
var x3, >= 0, integer;
var x4, >= 0, integer;
var x5, >= 0, integer;
var x6, >= 0, integer;
var x7, >= 0, integer;
var x8, >= 0, integer;
var x9, >= 0, integer;
var x10, >= 0, integer;
var x11, >= 0, integer;
minimize obj: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11;
s.t. ca: 4*x1 + 6*x2 + 8*x3 + 6*x4 + 2*x5 + 3*x6 + 3*x7 +                   4*x10           >= 80;
s.t. cb:                      2*x4 + 2*x5 +        1*x7 +        2*x9 + 2*x10 + 3*x11 >= 80;
s.t. cc: 4*x1 + 2*x2 +               3*x5 + 4*x6 + 3*x7 + 6*x8 + 4*x9 + 2*x10 + 4*x11 >= 80;
solve;
display x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11;
end;

The eleven decision variables reflect, how many boards should be cut according to the given configuration.

GLPK came up with the following solution, using just three of the eleven cutting configurations:

 8 x type  4 yields 48 x A, 16 x B 
 8 x type 10 yields 32 x A, 16 x B, 16 x C
16 x type 11 yields         48 x B, 64 x C
total               80 x A, 80 x B, 80 x C

A: 80 pieces sized 50cm x 60cm

B: 80 pieces sized 50cm x 70cm

C: 80 pieces sized 60cm x 70cm 

According to this solution, 32 wooden boards are needed.