Bin Packing Problem

[jfarr3ll]

Hi all,

I'm struggling with a specific bin packing problem...

I have a dataset where there is a column which identifies certain records. i.e. the cell takes a value 1 if the record needs including and 0 if not.
There is also a column which gives a number of parts needed. i.e. 1.56 or 2.73 etc.

What I'm trying to do is split the records into batches of 4 to minimise wastage. So I need a code to look at the identifier column and then group together those records identified in the groups which minimise wastage according to the number of parts column.

So ideally the output would be something like:

group 1: A D E P
group 2: B C F G

etc...

I'm sure this must be possible, but can't figure it out. Any help would be greatly appreciated. It seems to be different to the other bin packing problems I've seen as the desired outcome is any whole number not a specified value.

[Guido Geurs]

Is it possible to attach in Bytes the workbook with a part of the records (+- 10) if there are to much ?
If the data is confidential, replace it with fictive values.

[jfarr3ll]

Hi Guido Geurs


This is a dummy workbook to show the structure

[Guido Geurs]

Is it possible to give an example according to the attached "repair dummy.xls" what you want to see?

[jfarr3ll]

Sorry I don't think I explained myself very well.

I'm looking for a code which will identify from column L which machines need a repair and then use column K to calculate the 4 machine combinations of these machines which minimises total wastage.

I may have been misleading talking about whole numbers as I think they're not necessarily what I need. (You can probably tell this is a bit above my skill level).

So ideally the end result would show the groups of ID's (from column E) and the total wastage.

i.e. group 1: G H J K
group 2: P I L M...
Total Wastage: x units.

Thanks for looking at this.

[Guido Geurs]

I hope this is it: (see also attachment)

Sub Filter()
Dim ARRselected() As SELECTION
Dim ARRidx As Integer
Dim GROUPcount As Integer
Dim ARRdump() As Variant
Dim TOTALWASTAGE As Double
Dim REPLACEbit As Border
    Worksheets("Sheet1").Activate
    Range("E3").Activate
    ReDim ARRselected(0)
    GROUPcount = 0
'§ collect data
    Do While ActiveCell.Value <> ""
        '§ if "Refill"
        If ActiveCell.Offset(0, 7).Value = 1 Then
            ReDim Preserve ARRselected(UBound(ARRselected) + 1)
            ARRselected(UBound(ARRselected)).MACHid = ActiveCell.Value
            ARRselected(UBound(ARRselected)).WASTAGE = ActiveCell.Offset(0, 6).Value
            GROUPcount = GROUPcount + 1
        End If
        '§ add blanco line if group=4
        If GROUPcount = 4 Then
            '§ add line for total group
            ReDim Preserve ARRselected(UBound(ARRselected) + 1)
            '§ total of the group
            ARRselected(UBound(ARRselected)).MACHid = "Total"
            ARRselected(UBound(ARRselected)).WASTAGE = _
                    ARRselected(UBound(ARRselected) - 4).WASTAGE + _
                    ARRselected(UBound(ARRselected) - 3).WASTAGE + _
                    ARRselected(UBound(ARRselected) - 2).WASTAGE + _
                    ARRselected(UBound(ARRselected) - 1).WASTAGE
            TOTALWASTAGE = TOTALWASTAGE + ARRselected(UBound(ARRselected)).WASTAGE
            ReDim Preserve ARRselected(UBound(ARRselected) + 1) '§ add blanco line
            GROUPcount = 0
        End If
        '§ goto next record
        ActiveCell.Offset(1, 0).Activate
    Loop
    '§ add final total
    ReDim Preserve ARRselected(UBound(ARRselected) + 1) '§ add blanco line
    ReDim Preserve ARRselected(UBound(ARRselected) + 1) '§ add blanco line
        ARRselected(UBound(ARRselected)).MACHid = "TOTAL"
        ARRselected(UBound(ARRselected)).WASTAGE = TOTALWASTAGE
'§ dump data
    '§ transform ARRSELECTED to 2D array
    ReDim ARRdump(1 To UBound(ARRselected), 1 To 2)
    For ARRidx = 1 To UBound(ARRselected)
        ARRdump(ARRidx, 1) = ARRselected(ARRidx).MACHid
        ARRdump(ARRidx, 2) = ARRselected(ARRidx).WASTAGE
    Next
    '§ dump to sheet2
    Sheets("sheet2").Activate
    Range("A1").Resize(UBound(ARRdump), 2) = ARRdump
    '§ clear cells with zero
    Worksheets("Sheet2").Columns("B").Replace What:="0", Replacement:="", _
        SearchOrder:=xlByColumns, MatchCase:=True, lookat:=xlWhole
End Sub

[jfarr3ll]

Thank you for this the code looks good, but it doesn't quite do what I was looking for. It seems to just work down grouping the records by row order not by minimal wastage.

Is there a way to tweak it so that it examines all the records and then groups them according to least wastage not just in order?

[Guido Geurs]

it must be= ??

G 1.62
K 1.74
P 1.8
L 2.31

H 2.82
J 2.97
M 3.3
N 4.35

[jfarr3ll]

these are the results I get when I run the filter macro...

G 1.62
H 2.82
J 2.97
K 1.74
Total 9.15

L 2.31
M 3.3
N 4.35
P 1.8
Total 11.76


TOTAL 20.91


Are you getting different results?

[Guido Geurs]

I have the same results but in your previous mail you are mentioning:
"...and then groups them according to least wastage not just in order? "
Is it sorted what you want? like=
G 1.62
K 1.74
P 1.8
L 2.31

H 2.82
J 2.97
M 3.3
N 4.35

Or how do you want them sorted?
Please tell me what you just want with the file you have attached (with an example list).

[jfarr3ll]

I am missing the step From getting them in order to sorting into the groups of 4 to produce the least wastage.

for example if I changed the values column K as follows:

record G = 1.3
record H = 1.2
record M = 1.3
record P = 1.2

I was hoping the code would identify that this combination would produce zero wastage and group them together.

I thought I'd add for clarity that my definition of least wastage would be the group producing as close to a whole number as possible

Again thank you so much for your help on this.

[Guido Geurs]

Is this right, you want to see only the 4 data with the least wastage number:

G 1.62
K 1.74
P 1.8
L 2.31

If not, please attach the workbook with in sheet1 the data and in sheet2 the results you want to see.
Sorry but it's a little confusing for me.

[jfarr3ll]

sorry this is my inability to express myself fully.

What I want to see is all the data split into groups of 4 where the sum of all the values in each group are as close to a whole number as possible.

In this way we can share packs of parts across the group and waste fewer packs.

I think the central assumption is that without grouping a repair requiring 1.3 parts would need 2 packs and waste .7 of a pack.

Therefore if 4 packs can be grouped by how close to a whole number the sum of the parts required is, savings can be made.

I have tried to demonstrate on sheet 2.... (I have modified the numbers to make this easier to calculate by hand)

[Guido Geurs]

I hope this is the code you are looking for (see attachment)
PS:
I have changed some values to check if a group with total fraction=0 is selected first.
I can send you an explanation (drawing) of the code if necessary because I have used several array.

[jfarr3ll]

That looks perfect. I can't thank you enough. If you wouldn't mind sending the explanation that would be v useful for me.

[Guido Geurs]

Attached are some flowcharts of the code.

[Guido Geurs]

This is a version working on the same principle but with the indexes of the ARRSEL array.
Maybe a little faster with large sheets

[jfarr3ll]

That's perfect. Thank you so much for this.

[jfarr3ll]

Hi Guido,

Last year you were increadibly helpful with this problem, and I was hoping you could provide some of your expertise again to help with a slight issue I've identified when using your code in practise.

It is perfect as long as a multiple of 4 is not entered. However, when a multiple of 4 is entered it seems to ignore one record.

Alternatively if anyone else can help I'd greatly appreciate it.

I have attached a workbook.

Many Thanks in advance,

[Guido Geurs]

Sorry, my mistake.
For the last records there is an error in the code.
There is 2 times "Case 3" so If there are 4 records left, the 4th will never be seen.
It must be:

.....
                Case 3
                    .INDEX3 = ARRSELidx
                Case 4
                    .INDEX4 = ARRSELidx
                End Select
            End With
.....

[jfarr3ll]

perfect.

Thanks again Guido.