Distribute Lengths without loss

[John Cole, Jr.]

I have the need to take several lengths of pipe and break them up into
several smaller pieces. The problem is I need to be able to match them
up eliminating as much loss as possible. For example, I have 5 pieces
of pipe. They are 40', 27', 32', 15' and 9' long. I have to cut these
into 25 pieces of various smaller lengths. I need to be to do that
without leaving too many unusable pieces left over. If two of teh ones
I need are 16' and 10' then I would want to assign them to the 27' long
piece because it only cause me to lose 1'. Can anyone help me with
this?

I am pretty good with VBA, and I'm a very experienced Excel user. I
just don't even know where to begin with something like this.

Thanks for the help in advance!!!

 

[Anthony D]

Hi John,

This may well be a 'hard' problem requiring specialised algorithms to get
the optimal solution in all cases.
If two pieces are 16' and 10', this leaves 97' in total for 23 pieces ?

Without knowing the lengths required, would perhaps one approach be to sort
both the available pipe lengths and the 25 required pipe lengths into
increasing length order and then match up the smallest required with the
smallest available ?

Anthony

 

[ר×ובן]

hi john
there is a way to find optimal solution for your problem.try to find an
"Operations Research" proffesional, thats his job.
the method is called "Simplex" and you need to build a series of equations
(called restrictions) and solve them so that the total loss is minimal.
to build these restriction eqautions you need to build all the posiible
combinations (i.e.: 40' can be cut into 16' and 10', and you loose 14' etc.)
note:
1)an optimal solution exits and there is an algorithms to calculate it.
2) if you want to program it from scratch you have to invest a lot of time.
i assume you can find of the shelf software
3) Microsoft Excel has an add on (included in excel) named "Solver". load it
with <tools><addon> use help to find how it works. they have also a reach
example file included.
good luck
reuven

 

[HSalim[MVP]]

You could post a query in the sci.math newsgroup.

In anything that involves permutations and combinations, the number of
possibilities grows exponentially as the number of inputs increases.
While it might be a difficult or expensive(too many calculations) to find
the "best possible" answer, you can easily achieve a good-enough solution.
For example, pass 1 tries to find that are identical matches between output
and input. - you want a 9 foot pipe, I got one
next find all combinations where sum of one or more outputs equals one
input - you want a 3 +2, I have a 5
in pass threee, you cut the rest.

But this does account for "common sense" strategies.
For example, common sense knows that if the need is for one 3 foot and one 4
foot pipe, it is better to cut these lengths from two different pipes that
are 9ft long because 6ft and 5ft pipes may be used in the next job, while a
2 foot pipe may be rarely used or is a waste.

To account for that, you may need to build an even more complex model - at
what point do you say you would rather waste 2ft than to carry more 5ft and
6ft lengths.

HS

 

[John Cole, Jr.]

Thanks for the help, but I'm never going to be able to do what is
necessary. What about a shortcut. Let's say Column "A" has the
lengths I need while Column "B" has the Lengths available. Is there a
way I can run a macro to take the longest length in A, assign it to
longest in B, therefore shrinking that pipes length. Then take the
second is column A and assign it to the next longest and so on. When
part of a length is used, it should be placed back in the selection
group with the length previously taken subtracted from it. This would
be some form of a loop.

JC

 

[Anthony D]

Hi John,

I don't think there is a particularly straightforward macro.
Perhaps a table might help in the first instance, sorted by ascending
lengths required and ascending lengths available (here left to right) so that
shortest pieces can be used first to minimise wastage. (An example with 5
lengths)

required supplied available total
36 36 9 15 27 32 40 123

2 2 -2 -2
3 3 -3 -3
5 5 -5 -5
10 10 -10 -10
16 16 -16 -16
etc.

remaining 4 0 11 32 40 87


Anthony

 

[Anthony D]

(re-post, hopefully format better)

required supplied available total
36 36 9 15 27 32 40 123

2 2 -2 -2
3 3 -3 -3
5 5 -5 -5
10 10 -10 -10
16 16 -16 -16
etc

remaining 4 0 11 32 40 87