Optimising Pipe Cutting 1

[mgp]

A colleague of mine have been asked if he could establish a computer program for optimising usage of pipes when cutting.

The problem:

Pipes on stock exist in a number of random lengths, typically 6m but with some variations.

Pipes for fabrication needs to be cut into specific lengths normally smaller than random length.

Find out which combination of the required cut lengths shall be selected for each pipe length on stock, in order to minimise scrap material.

I'm not sure if this is the right forum for this, but I would appreciate if anyway could anyone point which mathematical method to use for this.

regards
Mogens

 

[nbucska]

The biggest problem is entering the lenghts -- or keeping
track of the individual pipes. If e.g. I cut off 1ft
from a 6 feet pipe, the program has to remember that it is 5
feet and where it can be found.

Any suggestion ? The programming is simpler...
<nbucska@pcperipherals.com>

 

[ve7brz]

Hi,

I thought I'd responded to this before, but perhaps I neglected to send the response. Anyway, I suggest that you look to the forest industry, as programs of this nature are widely used in sawmills.

 

[flamby]

What you are referring to is a very common problem and referred as &quot;one dimensional bin packing problem/ algorithm&quot;. Do an internet search, you will fing both the algorithm as well as some programs. This name apparently came from packing industry where they wanted to optimise number of differenly sized bins for packing odd sized pipes and this is very relevent for you also.
Hope it helps.
flame

 

[mgp]

Thanks flame for the hint - there seems to be a lot of links with this search.

To Bruce (ve7brz)
You did in fact respond before.
I resubmitted my question to this forum due to your advice in your last response - with good result, thanks.

regards
Mogens