Algorithm Logic Help...

[cptHotkeys]

Hi, I need to make a class for calculating the most efficient use of lengths of steel, there may be many different lengths to cut the bars into and each length may have a different quantity.
The goal is to minimize the size of the offcuts and reduce the amount of lengths needed..

E.g :
Material = 50mm wide * 10mm thick @ 6000mm long
400pcs Cut @ 1092mm
400pcs Cut @ 910mm


I have created a class which can calculate the lengths required for a individual item but I am stumped at how to go about finding the most efficient use of lengths. The class I have created is the following...

Public Class Cut
    Private dblLength As Double     'Length of material
    Private dblCutLength As Double  'Length to cut at
    Private intQTY As Integer		'Quantity to cut

    Sub New(ByVal TotalLength As Double, ByVal CutLength As Double, ByVal QTY As Integer)
        dblLength = TotalLength
        dblCutLength = CutLength
        intQTY = QTY
    End Sub

    Public Property Length() As Double
        Get
            Return dblLength
        End Get
        Set(ByVal value As Double)
            dblLength = value
        End Set
    End Property

    Public Property CutLength() As Double
        Get
            Return dblCutLength
        End Get
        Set(ByVal value As Double)
            dblCutLength = value
        End Set
    End Property

    Public Property QTY() As Integer
        Get
            Return intQTY
        End Get
        Set(ByVal value As Integer)
            intQTY = value
        End Set
    End Property

    ''' <summary>
    ''' Calculates the total cuts of CutLength available in Length
    ''' </summary>
    Public Function CutsPerLength() As Integer
        Return Math.Floor(CInt(Length / CutLength))
    End Function

    ''' <summary>
    ''' Calculates and returns the total offcut after the maximum cuts of CutLength have been made in Length
    ''' </summary>
    Public Function OffCut() As Double
        Return (((Length / CutLength) - Math.Floor(Length / CutLength)) * CutLength)
    End Function

    ''' <summary>
    ''' Calculates and returns the total Lengths required to acheive the quantity desired
    ''' </summary>
    Public Function LengthsRequired() As Integer
        Return Math.Ceiling(QTY / CutsPerLength())
    End Function

End Class

Now the next part is to create a class which will have a list of Cut and determine optimum number of each cut length which can be cut off a length to maximize steel efficiency, is some cases there may be several different lengths to cut off one bar, in other cases there may be only one length to cut the bar into, I also need a list of next best alternatives as in some cases the inconvenience of having to make too many seperate cuts will out weigh the benifits of saving some money on the cost of a few extra bars of steel...

Thanks in advance...

[jmcilhinney]

This isn't a VB.NET question. Implementing an algorithm in VB.NET is a VB.NET question. Coming up with an algorithm in the first place is a pure mathematics question and has nothing to do with any specific programming language. This site has a maths forum, but I'm quite sure that you could find such an algorithm somewhere on the Web already. It might take a bit of work to come up with the right search key words, but solving problems is what we do.

[cptHotkeys]

Yeah, I have tried to search but to no avail, Guess I will keep trying then.

Thanks

[jmcilhinney]

I'm sure that this problem has a specific name in maths circles but I don't recall it if I ever heard it. You really should try the maths forum. Ask a mod to move this thread.

[Shaggy Hiker]

The problem does indeed have a specific name: The Backpack Problem.

The situation is generally described as having a known volume, and a variety of different sized items, and you want to know the optimum set of items to load based on some optimization criteria.

Now for the bad news: The problem may have no definitive solution, and certainly doesn't have an easy one. I have read articles that used this problem as a target for a Genetic Algorithm, showing how a nonlinnear routine like that could be used to solve the problem. You wouldn't be seeing something like that if there was a trivial algorithm that would give you the answer. Basically, you have asked a question that is so difficult that it has been the subject of rigorous mathematical study for decades. Good Luck.

You might decide that an optimal solution will not present itself without use of some kind of nonlinnear search like a GA, which could take considerable time to reach a solution (one of my GAs takes three days to complete, despite being relatively tightly written), and therefore you could try to settle for a "good enough" solution, which could be hideously inefficient in certain situations. For instance, take the longest piece first, find the smallest stock that is larger than that, then go for the next longest, etc. It will be woefully inefficient, though.

[cptHotkeys]

Yeah, I figured there was more depth to this than I realized.
I do have an idea that will provide a better than nothing solution, a rather brutish aproach which involves an infinite loop running on a thread which will basicaly attempt every possible combination which does not exceed the maximum number of the smallest cut that will be possible, calling back to the main thread when the current combination is better than the current best, or trying a new combination when it has exceeded the maximum bar length, ultimately killing the thread when all possible combinations have been calculated which do not exceed the maximum number of the smallest cut that will be possible...

Bit of a head scramble, maybe i am biting more than I can chew.

Would I be correct in saying that the maximum number of combinations would not exceed the number of cuts that can fit into one length of the smallest cut to the power of n(cuts)???

E.g: 1800pcs @ 230mm, 2300pcs @ 343mm, 5500pcs @ 565mm (three different cut lengths)
Material length is say 2300mm.
thats 100 230mm peices per length.

which means the maximum number of combinations does not exceed
100 to the power of 3 = 1000000 combinations.

Thats a pretty grim situation when a user may want to run this algorithm with 50 different cut lengths which is 1.e+100; the jobs would have been given to another company by the time the algorithm has finished...

[Shaggy Hiker]

Your suggestion gives me a bit of an idea. I'll think about it more later on today (as I drive across the state with nothing better to do).

[Shaggy Hiker]

I spent some time thinking about this, and have come up with a genetic algorithm approach that could find solutions to the general problem:

Need: to get a set of N items of length L, N1 items of length L1, N2 items of length L2, etc., from a selection of stock items of various known lengths. Find: a solution which minimizes either total length or total pieces of scrap.

I suspect that I could create the entire program this weekend, but it would probably take several hours to run through anything other than a trivial situation. Since the question comes up every now and then, I might make the thing just to play with it. Would it be of use to you? How about if the code took three hours to find a solution? How about six hours?

This would actually be a problem that a coding contest could be built around. Either coming up with a solution to the problem, or taking an existing program (such as the one I am considering writing), and tweaking it to optimize speed.

[MaximilianMayrhofer]

This interests me, but I may be really really slow because i'm still not 100% sure what the problem is asking exactly. I'm kind of getting this impression:

I need a bar of length X.

I have bars of length A, B and C.

What is the combination of bars A, B and C that will yield a bar X with the minimum of wasted metal from having to trim one of the bars in the combination?

Correct?

[Shaggy Hiker]

That would be a great simplification. Consider that you have several stock bars (N1 - Nx). You need some number of length L1, another number of length L2, etc. Which stock bars do you use (N1-Nx), and in what quantity, such that the amount of waste is minimized.

[Jenner]

I don't think he needs to get into the complexity of multiple sized stock bars. The dynamics may also change as you proceed to cut bars:

"I have an infinite number of bars. All X long"
I need to cut these bars. I need 100 that are Y length and 100 that are Z length.

The problem: How many Y's and Z's of each type can I cut a X length bar into so I have the minimal amount of leftover material.

Example: With 100 Y's and 100 Z's, I find with 2 Y's and 5 Z's, I've only got this tiny piece of leftover material from X. Surely, 2 Y's and 5 Z's is the BEST way to divide up an X bar.

But what happens when I run out of Z's since I'm using 5 at a time? Eventually, I'll have nothing but Y's, and I may find that I can only fit 3 Y's in a single X, and I have a LARGE piece left over!

Maybe 3 Y's and 2 Z's produce less scrap overall?

Is there a more efficient way to divide them up so the total amount of scrap after I'm done cutting all my Y's and Z's is minimal?

Complex problem. This would make a math junkie drool.

[Shaggy Hiker]

I have a solution based on a variety of different Xs (since the OP specified that there would not be a single length required). My solution is based on an infinite number of stock bars, such that if it is decided that the most efficient solution is to make all the cuts out of stock bar B, then I assume sufficient bar B to make ALL the cuts. The solution assumes that one of the inputs will be the stock, which will be a list of available stock lengths, but will assume an infinite number of each one.

Altering this such that the number of available pieces at each length is capped would be possible, and the underlying code wouldn't really change much, but I'm not going there unless I need to.

The problem is sufficiently interesting that I am planning to spend most of tomorrow working it up.

[cptHotkeys]

The more I think about this, the more complex it gets.
By the way, in most manufacturing environments the total offcuts does not matter as much as the size of individual offcuts, say you may have 20,000 50mm offcuts, vs 100 500 mm offcuts, the 100 500mm offcuts are of more importance to reduce as a larger size is generaly more usable.

Total length of bar 1000mm

L1 = 95mm, qty = 200, max bars allowed = 20, offcut of 50mm per bar
L2 = 195mm, qty = 344, max bars alowed = 70, offcut of 25mm per bar
L3 = 550mm, qty = 50, max bars allowed = 50, offcut of 450mm per bar

In a typical manufacturing\production environment, a job which required the lengths mentioned above cut from the bar mentioned above would be costed by using the total max bars allowed, which in this case is 140. So there should be no money lost if there is no algorithm (or human brain) to find the best combination. However an organisation with a fairly large output of such goods could stand to make a much greater profit or become more competitive if the bars that were not used are returned to stock and used in a later job.

[cptHotkeys]

[QUOTE=Shaggy Hiker]
Altering this such that the number of available pieces at each length is capped would be possible, and the underlying code wouldn't really change much, but I'm not going there unless I need to.
QUOTE]
Yes, and in a case when the a cut length reaches its quantity could be removed from the equation and the algorithm could be run again, but I guess you know this...

Thanks shaggy