473,836 Members | 1,521 Online

# Bin Packing Problem

11 New Member
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.
Apr 2 '12
20 5508
jfarr3ll
11 New Member
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.
Apr 4 '12 #11
Guido Geurs
767 Recognized Expert Contributor
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.
Apr 4 '12 #12
jfarr3ll
11 New Member
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)
Attached Files
 repair dummy_v1.xls (55.5 KB, 344 views)
Apr 4 '12 #13
Guido Geurs
767 Recognized Expert Contributor
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.
Attached Files
 repair dummy_v3.4.xls (74.0 KB, 331 views)
Apr 5 '12 #14
jfarr3ll
11 New Member
That looks perfect. I can't thank you enough. If you wouldn't mind sending the explanation that would be v useful for me.
Apr 6 '12 #15
Guido Geurs
767 Recognized Expert Contributor
Attached are some flowcharts of the code.
Attached Files
 Visio-repair dummy_v3.4__v2.pdf (502.3 KB, 369 views)
Apr 7 '12 #16
Guido Geurs
767 Recognized Expert Contributor
This is a version working on the same principle but with the indexes of the ARRSEL array.
Maybe a little faster with large sheets
Attached Files
 repair dummy_v4.1.xls (73.0 KB, 324 views)
Apr 7 '12 #17
jfarr3ll
11 New Member
That's perfect. Thank you so much for this.
Apr 10 '12 #18
jfarr3ll
11 New Member
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.

Attached Files
 repair dummy_v5.xls (1.78 MB, 368 views)
May 7 '13 #19
Guido Geurs
767 Recognized Expert Contributor
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:
Expand|Select|Wrap|Line Numbers
1. .....
2.                 Case 3
3.                     .INDEX3 = ARRSELidx
4.                 Case 4
5.                     .INDEX4 = ARRSELidx
6.                 End Select
7.             End With
8. .....
Attached Files
 repair dummy_v5.0.xls (1.77 MB, 466 views)
May 9 '13 #20