Linear Nesting

SOULOUKALE

New Member
Joined
Dec 1, 2022
Messages
9
Office Version
  1. 2013
Platform
  1. Windows
Here is what I have, column A is the name of my items, column B is the quantity of the items, column C is their length, cell D2 is the length between items (width of the cut). column E is the quantity of bar, column F is their length.

1677169428710.png


I need a code that does a linear nesting of the items and outputs the result somewhat like:

BAR 1: 1x D, 2x E, 3x B, 3x C, 2x F

BAR 2: 1x C, 2x A, 4x F

any ideas? thanks :D
 

Excel Facts

Show numbers in thousands?
Use a custom number format of #,##0,K. Each comma after the final 0 will divide the displayed number by another thousand
This could be neater, but try:

VBA Code:
Sub BarCut()
Dim Rng As Range, sav As Variant, MyData As Variant, ctr(1 To 9999) As Long, bl As Double, ic As Double
Dim i As Long, j As Long, str1 As String, bool As Boolean

    Set Rng = Range("A2:C" & Cells(Rows.Count, "A").End(xlUp).Row)
    sav = Rng.Value
       
    With ActiveSheet.Sort
        .SortFields.Clear
        .SortFields.Add2 Key:=Range("C2"), Order:=xlDescending
        .SetRange Rng
        .Header = xlNo
        .Apply
    End With
   
    MyData = Rng.Value
    Rng.Value = sav
   
    For i = 1 To Range("E2").Value
        bl = Range("F2").Value
        ic = Range("D2").Value
        Erase ctr
        Do While bl > 0
            For j = 1 To UBound(MyData)
                If MyData(j, 2) > 0 And MyData(j, 3) <= bl Then
                    ctr(j) = ctr(j) + 1
                    bl = bl - MyData(j, 3) - ic
                    MyData(j, 2) = MyData(j, 2) - 1
                    Exit For
                End If
            Next j
            If j > UBound(MyData) Then Exit Do
        Loop
       
        str1 = "Bar " & i & ":  "
        For j = 1 To UBound(MyData)
            If ctr(j) > 0 Then str1 = str1 & ctr(j) & " X " & MyData(j, 1) & ", "
        Next j
        str1 = str1 & "Leftover: " & bl
        Range("H1").Value = "Results"
        Range("H100").End(xlUp).Offset(1).Value = str1
    Next i
                   
    bool = False
    str1 = "Not made: "
    For i = 1 To UBound(MyData)
        If MyData(i, 2) > 0 Then
            bool = True
            str1 = str1 & MyData(i, 1) & " X " & MyData(i, 2) & ", "
        End If
    Next i
    If bool Then Range("H100").End(xlUp).Offset(1).Value = str1
   
End Sub

This turned this:

Book1
ABCDEF
1NameQtyLengthInner CutBar QtyBar Length
2A2100.3752200
3B320
4C415
5D130
6E225
7F65
Sheet5


Into:

Book1
ABCDEFGH
1NameQtyLengthInner CutBar QtyBar LengthResults
2A2100.3752200Bar 1: 1 X D, 2 X E, 3 X B, 3 X C, 1 X A, Leftover: 1.25
3B320Bar 2: 1 X C, 1 X A, 6 X F, Leftover: 142
4C415
5D130
6E225
7F65
Sheet5


Also note that this uses a "greedy" algorithm, meaning it tries to pick the biggest remaining piece to use next. Depending on the sizes, this may not result in the most efficient use of the bar stock.
 
Upvote 0
Hi Eric! This work great :D, but forgot to say that the bars can be of different lengths. Do you think it's possible to make the code work with multiples bar length? thanks!
1677246885419.png
 
Upvote 0
Try this:

VBA Code:
Sub BarCut()
Dim Rng As Range, sav As Variant, MyData As Variant, ctr(1 To 9999) As Long, bl As Double, ic As Double
Dim i As Long, j As Long, str1 As String, bool As Boolean, bn As Long, r As Long, barnum As Long

    Set Rng = Range("A2:C" & Cells(Rows.Count, "A").End(xlUp).Row)
    sav = Rng.Value
        
    With ActiveSheet.Sort
        .SortFields.Clear
        .SortFields.Add2 Key:=Range("C2"), Order:=xlDescending
        .SetRange Rng
        .Header = xlNo
        .Apply
    End With
    
    MyData = Rng.Value
    Rng.Value = sav
    barnum = 1
    Range("H:H").ClearContents
    
    For r = 2 To Range("E999").End(xlUp).Row
    For i = 1 To Cells(r, "E").Value
        bl = Cells(r, "F").Value
        ic = Range("D2").Value
        Erase ctr
        bool = False
        Do While bl > 0
            For j = 1 To UBound(MyData)
                If MyData(j, 2) > 0 And MyData(j, 3) <= bl Then
                    ctr(j) = ctr(j) + 1
                    bl = bl - MyData(j, 3) - ic
                    MyData(j, 2) = MyData(j, 2) - 1
                    bool = True
                    Exit For
                End If
            Next j
            If j > UBound(MyData) Then Exit Do
        Loop
        
        If bool Then
            str1 = "Bar " & barnum & ":  "
            For j = 1 To UBound(MyData)
                If ctr(j) > 0 Then str1 = str1 & ctr(j) & " X " & MyData(j, 1) & ", "
            Next j
            str1 = str1 & "Leftover: " & bl
            Range("H1").Value = "Results"
            Range("H100").End(xlUp).Offset(1).Value = str1
            barnum = barnum + 1
        End If
    Next i
    Next r
                    
    bool = False
    str1 = "Not made: "
    For i = 1 To UBound(MyData)
        If MyData(i, 2) > 0 Then
            bool = True
            str1 = str1 & MyData(i, 1) & " X " & MyData(i, 2) & ", "
        End If
    Next i
    If bool Then Range("H100").End(xlUp).Offset(1).Value = str1
    
End Sub

This was my test sheet:

Book1
ABCDEFGH
1NameQtyLengthInner CutBar QtyBar LengthResults
2A2100.375280Bar 1: 1 X D, 1 X E, 1 X B, Leftover: 3.875
3B320340Bar 2: 3 X E, Leftover: 3.875
4C415Bar 3: 1 X B, 1 X C, Leftover: 4.25
5D130Bar 4: 1 X B, 1 X C, Leftover: 4.25
6E425Bar 5: 2 X C, 1 X F, Leftover: 3.875
7F65Not made: A X 2, F X 5,
Sheet5


I'd recommend putting the bars in decreasing lengths. I thought about sorting the column by length, but that would affect the numbering. Let me know how this works.
 
Upvote 0
Hi Eric, this works well exept that I noticed that the nesting could be improved by adding a condition within the greedy algorithm. Here's what mean:

NameQtyLengthInner CutBar QtyBar LengthResultsLENGTH USED
M10165355010516000Bar 1: 4 X M1016, Leftover: 1760
16000​
M101853400515000Bar 2: 1 X M1016, 3 X M1018, Leftover: 2210
16000​
M102183100513000Bar 3: 2 X M1018, 2 X M1021, Leftover: 2960
16000​
510000Bar 4: 5 X M1021, Leftover: 450
16000​
Bar 5: 1 X M1021, Leftover: 12890
16000​


When you look at the length of the stock bars, there's 16 000, 15 000, 13 000 and 10 000. Since the greedy algorithm starts with the longest bars, the result is 5 bars of 16 000. But it could be:

bar 1: 15000
bar 2: 15000
bar 3: 15000
bar 4: 16000
bar 5: 10000

The condition could be after looping the str1, if the total length used is less than the next shorter stock bar, then use this one. The bar 1 is 14240 total used length wich is less than 15000 so use a 15 000 bar instead. I don't really know how to write that down or even if it's possible to incorporate that into the greedy algorithm.. Beside of that, I think it works like a charm!
 
Upvote 0
Lightly tested, but this incorporates your request. The bar stock must be in descending sizes or you'll get weird results.

VBA Code:
Sub BarCut()
Dim Rng As Range, sav As Variant, MyData As Variant, ctr(1 To 9999) As Long, bl As Double, ic As Double
Dim i As Long, j As Long, str1 As String, bool As Boolean, bn As Long, r As Long, barnum As Long
Dim bars As Variant, barqty As Long, itemqty As Long

    Set Rng = Range("A2:C" & Cells(Rows.Count, "A").End(xlUp).Row)
    sav = Rng.Value
        
    With ActiveSheet.Sort
        .SortFields.Clear
        .SortFields.Add2 Key:=Range("C2"), Order:=xlDescending
        .SetRange Rng
        .Header = xlNo
        .Apply
    End With
    
    MyData = Rng.Value
    Rng.Value = sav
    barnum = 1
    Range("H:I").ClearContents
    
    itemqty = WorksheetFunction.Sum(Range("B2:B100"))
    barqty = WorksheetFunction.Sum(Range("E2:E100"))
    ic = Range("D2").Value
    Range("H1").Value = "Results"
    Range("I1").Value = "Length used"
    
    bars = Range("E2:F" & Range("E999").End(xlUp).Row).Value
        
    Do While itemqty > 0 And barqty > 0
    
        For i = 1 To UBound(bars)
            If bars(i, 1) > 0 Then
                bl = bars(i, 2)
                Exit For
            End If
        Next i

        barused = 0
        Erase ctr
        bool = False
        Do While bl > 0
            For j = 1 To UBound(MyData)
                If MyData(j, 2) > 0 And MyData(j, 3) <= bl Then
                    ctr(j) = ctr(j) + 1
                    bl = bl - MyData(j, 3) - ic
                    barused = barused + MyData(j, 3) + ic
                    MyData(j, 2) = MyData(j, 2) - 1
                    bool = True
                    itemqty = itemqty - 1
                    Exit For
                End If
            Next j
            If j > UBound(MyData) Then Exit Do
        Loop
        
        If bool Then
            str1 = "Bar " & barnum & ":  "
            
            For i = UBound(bars) To 1 Step -1
                If bars(i, 2) > barused Then
                    bars(i, 1) = bars(i, 1) - 1
                    barqty = barqty - 1
                    Range("I100").End(xlUp).Offset(1).Value = bars(i, 2)
                    bl = bars(i, 2) - barused
                    Exit For
                End If
            Next i
            
            For j = 1 To UBound(MyData)
                If ctr(j) > 0 Then str1 = str1 & ctr(j) & " X " & MyData(j, 1) & ", "
            Next j
            str1 = str1 & "Leftover: " & bl

            Range("H100").End(xlUp).Offset(1).Value = str1
            barnum = barnum + 1
            
        End If
    
    Loop
                
    bool = False
    str1 = "Not made: "
    For i = 1 To UBound(MyData)
        If MyData(i, 2) > 0 Then
            bool = True
            str1 = str1 & MyData(i, 1) & " X " & MyData(i, 2) & ", "
        End If
    Next i
    If bool Then Range("H100").End(xlUp).Offset(1).Value = str1
    
End Sub
 
Upvote 0
Solution
Thanks a lot Eric! I was surprise of how little information I could find on linear nesting algorithm (greedy, column generation, best-fit etc..). Anyways thanks that helps a lot!
 
Upvote 0
Happy to help!

Also, about 26 lines from the end, this line:

VBA Code:
If bars(i, 2) > barused Then

should be:

VBA Code:
If bars(i, 2) >= barused - ic Then


That will let you pick the smaller bars in a few more cases. Also, it appears that this problem is a special case of a problem called "The Knapsack Problem." You might be able to find some more information on that. Good luck!
 
Upvote 0

Forum statistics

Threads
1,214,971
Messages
6,122,520
Members
449,088
Latest member
RandomExceller01

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top