473,836 Members | 1,521 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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


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
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
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
File Type: xls 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)
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
File Type: xls repair dummy_v3.4.xls (74.0 KB, 331 views)
Apr 5 '12 #14
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
File Type: pdf 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
File Type: xls repair dummy_v4.1.xls (73.0 KB, 324 views)
Apr 7 '12 #17
11 New Member
That's perfect. Thank you so much for this.
Apr 10 '12 #18
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.

Many Thanks in advance,
Attached Files
File Type: xls 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
File Type: xls repair dummy_v5.0.xls (1.77 MB, 466 views)
May 9 '13 #20

Sign in to post your reply or Sign up for a free account.

Similar topics

by: ZaGras | last post by:
after i pack my vb program using package and deployment wizard, i try to install the program on other computer instead of my computer and run the program. when i click to add a new record to the Microsoft Access database, the following error message was prompted out: item cannot be found in the collection corresponding to the requested name or ordinal. Error number: 3265 when i click on one button which will query the Microsoft Access...
by: j_mckitrick | last post by:
Hi all. Here is a tiny container for one of each combo box, along with the glade file. Just 2 widgets, so hopefully not too large. How the heck do I get the selection from the ComboBox, as opposed to the ComboEntryBox? I'm pulling my hair out over this one! jonathon
by: nobull | last post by:
Google won't let me post this as a follow-up but lynch@agere.com (lynto) wrote in message news:<503469eb.0407271148.7ee4b0ca@posting.google.com>... > Does anyone have an algorithm for packing registers? Algorithms are language independant so this question is off topic in comp.lang. It appears that you are taking about the famous "packing problem" which is, I believe, fairly trivially, mathematically equivalent to the even more...
by: Michael Olea | last post by:
Here is a design problem I ran into this am - and I have cleaned the bathroom, scrubbed toilet sink and tub, windexed all glass, mopped the floor, and vacuumed the house - no dice, the problem is still there. Maybe y'all have some ideas? Background ========== The basic idea behind templates, of course, is that much code is independent
by: gbb0330 | last post by:
Hi all I need some advice. the daily packing number will be used to match a box with its label. the guys in the warehouse will get a list of items to pack. they will find the item - put it in a box and click a button at this point the daily packing packing number will be genrated. the packing guy will write it on the box.
by: gbb0330 | last post by:
hi guys -the code (all capital letters) generates daily packing number, it is in the on click event of a command button that moves to the next record. dpkn is unbound control - i use it to display the last daily packing number genrated, so when the user moves to a new control they will know what the last daily packing number was. PdailyPackingNumber is bound and is 0 until the user clicks the button.
by: FMorales | last post by:
Hello all, quick hopefully easy question. Here goes. I've started on the Art Of Assembly tutorial(s) (http://webster.cs.ucr.edu/Page_asm/0_ArtOfAsm.html) and got to the sample projects and kinda got stuck. I'm needing to use a language of my choosing (which i easily chose C) to do this project where it wants me to pack data into a 16 bit variable. Now i am familiar with C to a pretty decent extent, just not bit manipulation. So what...
by: Edward Diener | last post by:
Is the packing alignment of __nogc classes stored as part of the assembly ? I think it must as the compiler, when referencing the assembly, could not know how the original data is packed otherwise. Yet, in my understanding, attributes are only __gc and __value class specific and do not apply to __nogc classes. Is this correct ? If so, how is the packing alignment of __nogc classes stored ?
by: fraz | last post by:
Does anyone have code to solve a 3-d bin packing problem in php? I am trying to solve the issue of packing various sized rectangular shaped objects into boxes of three different sizes so as to use as few packing peanuts as possible (to some reasonable approximation) to fill the gaps. I have found some c code and plenty of discussions on the subject, but I was thinking that someone out there has to have done this in php already.
by: QbProg | last post by:
Hello, what I'm saying here is about VS 2005 WITHOUT service pack. I have two DLL projects, with EXACTLY the same project preferences and settings. Both have alignment set to "default", it should be 8. Surpise number one: In project B I include a file of project A in this way #include <FILE_FROM_A.h>
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.