Board Optimisation Problem

[Mark_Pearl]

Okay here is a more details explanation of the problem.

Imagine if you were a carpenter, now as carpenter's go you are fairly hard working and hate to see waste. Thus when U see all the little pieces left over after cutting a large sheet of wood ("Board") into smaller pieces, U feel fairly sickned. What can U do.

U know the following,
1) All little pieces that U cut out of the board are smaller than the board's dimensions.

2)All the little pieces are of the same thickness, but have diffrent lengths and widths.

3)All the little peices are rectangular

4)It does not matter which direction U cut the board, (there is no grain)

5)U can have left over pieces, which is called wasteage

Task : design an algorithm that will draw the best possible method to cut board into smaller peices with the least wasteage.

If anyone can do this I will be reasonably impressed. Be original...

Good Luck

[Edited by Mark_Pearl on 01-08-2001 at 08:59 AM]

[paulw]

Errrr. If I knew what you were talking about, I might take it on. What is a board cut? Are we talking about making a box?

More enlightenment would definitely be a good thing.

P.

[Guv]

There seems to be something missing in the definition of this problem.

Must saw cut losses be considered? Are we dealing with enough pieces to require the use of more than one board?

If all the little pieces can be cut from a single board, the wastage is constant, unless you have to consider saw cut losses. You get the total area of the pieces and subtract from the area of the board. The difference is the wastage. In this case, you do not have an optimization problem.

Does the solution require knowing the width of a saw cut? For example, you cannot cut a 24 by 36 piece of plywood into four 12 by 18 pieces. You will end up with 11.875 by 17.875 pieces because a saw cut loses about .125 inches. In this situation, you have to know the width of a saw cut.

If the solution requires the use of more than one board, you have an optimization problem. In this case, it is easier to think of it as a packing problem. Imagine fitting 2D objects into 2D boxes. I once worked on a 3D version of this problem involving optimal packing of freight cars.

As of 30-40 years ago, a solution for the general 3D problem was not known. In practice, some simple algorithms could be used to obtain pretty good solutions which were acceptable in practice.

The 2D problem might be more amenable to a solution than the 3D problem I worked on.

[HarryW]

I think the point isn't to calculate the wastage, it's to find the optimal pattern. The problem isn't well defined though, so that's all I can tell.

[Mark_Pearl]

No, sorry maybe it is badly defined. It is not to calculate the wasteage... but rather to find the optimised fit, with the least possible wasteage left over...

[paulw]

Hmmm. At least I understand it now. Fit the most rectangles into another rectangle such that waste is kept to a minimum.

Interesting, particularly as I can't see a way to work infinity into this (parallel lines might be there somewhere, though:):)).

Cheers,

P.