bin packing problem

[agagelis]

Hi,
I'm trying to find an algorithm for online bin packing like problem...
I have some objects which i want to pack in boxes of min weight (5000)
My objects' weights are categorized :
100-200,
200-300,
300-400,
etc..

I have a max number of open boxes, let's say 15 and each box must be filled with at least 5000 but with objects of the same category!!

The problem is that the overweight must be as small as possible...

I have searched for existing algorithms but everything i found tries to fill boxes as much as possible to maximum weight!!

any suggestions ??

[BioPhysEngr]

The constraints seem wrongly specified. Do you mean to say that only one type of item (with a single weight) can be put in a box? If so, just figure out which one minimizes the remainder of 5000 / item_weight and pack all 15 boxes with that item.

Can you specify more clearly what you mean?

Otherwise, the solution may be amenable to linear programming (or, might be NP-complete; I'm not sure. see: https://en.wikipedia.org/wiki/Bin_packing_problem )

[agagelis]

Sorry for my english..
That's correct...
The problem is that by minimizing the remainder there is a chance that a box has less than 5000 which is forbidden.
the categories are gramms , so each box must have 5 Kilogramms.
I believe that this is an NP-complete problem as i have to do with items of unknown weight up until it's time for each item to be packed.
All bin packing like problems are trying to minimize the remainder. This is why I am asking for help.
Does anyone know an algorithm for a problem description as above????

[nuzzle]

Does anyone know an algorithm for a problem description as above????

For each category there's an optimal mix of objects that gives the smallest overweight. You select the category with the smallest overweight and fill every bin with it. That gives the smallest total overweight.

The result is that there's a best category and you will fill every bin with the same mix of object from that category. If that's not what you want you need some additional constraint.

[agagelis]

I'm not sure that i have explained it correctly..

We have 3 categories of objects .

A: 100-200 gr
B: 200-300 gr,
C: 300-400 gr.

So, objects of category A could weight 123gr or 298gr or whatever between 100-200 gr.(100 different possibilities!!)

We also have 15 boxes-buckets or whatever like these, in which we have to packet objects so as to have a minimum weight of 5000 gr in each bucket but each bucket as objects of the same category. If a bucket is full, we replace it with a new empty one until all objects are packed...

So for example , in the end we will have
10 buckets of category A objects,
8 buckets of category B objects,
13 buckets of category C objects.

Objects are generated randomly, and must be put in a bucket after their generation (online).

So each momment t we have an object X , of weight w and 15 open boxes (3 for category A,5 for category A,7 for category C, totally 15). I want an algorithm to decide to which of the w category open boxes i should pack X , so as when the box is full , to have minimum overweight!!


I'm sure that this problem is NP-complete, but there must be an algorithm as for bin -packing, to describe a solution, not the optimal for sure...

I hope this time i explained it correctly!!!!

[nuzzle]

Objects are generated randomly, and must be put in a bucket after their generation (online).

So each momment t we have an object X , of weight w and 15 open boxes (3 for category A,5 for category A,7 for category C, totally 15). I want an algorithm to decide to which of the w category open boxes i should pack X , so as when the box is full , to have minimum overweight!!

So objects arrive one by one and are immediately put in any of several bins where they stay?

It seems the object categories are independent. If you can handle one, say B, you can handle all in the same way.

I think the best approach is to first figure out what average overweight you would get if you fill just one bin at a time. You can do this by a simple simulation. Say you get 75 for the B-bins. Then you figure out if you can improve on this average by using some strategy to fill many bins at the same time. You could try this for example. It can also quite easily be checked out using a simulation.

1. When a B-object arrives put it in the B-bin that results in the smallest overflow. If such a bin exists replace it with an empty bin and repeat 1, otherwise continue with 2.

2. Put the B-object in the emptiest B-bin. Goto 1.

The idea is to create plenty of opportunity to fill bins below the overflow average for the bin category. It's not a standard solution but on the other hand I have a feeling it's not a standard problem either.

[nuzzle]

I've done a small simulation based on the algorithm in my previous post. Here are the results for A, B and C objects:

A: 77 43 37 36 36
B: 126 84 81 81 81
C: 190 145 143 142 142

The numbers are the average bin overweights when 1 to 5 bins are used. As one can see the algorithm settles quickly and it doesn't seem useful to use more than 3 bins.

In this problem it's probably best to view whole bins as random variables. A bin can contain a certain number of objects of one category. If objects are uniformy distributed over the weight range (like between 100 and 200 for an A category object) the sum will tend towards a Gaussian distribution (if there are sufficiently many objects in a bin, something like 10 would do). An A-object weights 150 on average and a whole bin with N objects weights N*150 on average.

The most important bins are those that weight close to the maximum weight, 5000. For an A-bin that will be bins with 33 and 34 objects. They will weight 4950 and 5100 on average, but only on average. They will vary according to a Gaussian distribution with some variance (which is possible to determine). Of all 33-bins some will overflow and some won't. The same with the 34-bins, some will overflow and some won't.

When objects are added to a bin it will overflow eventually. For A-bins it will most likely be as a 33-bin or a 34-bin. It could be other kinds of bins too but they would have to stray very far from their bin averages by chance and that would be very unlikely for a Gaussian distribution. So the set of overflowed bins will be a certain combination of mostly 33-bins and 34-bins resulting in a specific bin overflow average.

So the overweight distribution will be dominated by two bins which differ by just one object (in the A-object case it will be by the 33-bin and the 34-bin). The overweight distribution will be composed of the two superimposed Gaussians of these dominant bins. There will be contributions from bins with other object numbers but these will be much smaller. This effect can actually be visualized. I've plotted a frequency table showing the number of bins for each posssible overweight (in the A case an overweight can be from 0 to 200). The Gaussians of ordinary A-objects are too broad so they melt together but if objects are given a narrower variation around the 150 mean like 140-160 the overweight distribution shows two distinct peaks indeed.

The algorithm fills a certain number of bins at the same time. Having many bins available to select from the algorithm seems able to make a much more efficient choise than when each bin is filled one at a time. So the suggested strategy works although it may not be optimal.

Well it was an interesting little problem. It should be possible to analyze the algorithm formally treating bins like Gaussian random variables. If it's a real life problem I recommend the OP to do simulations and play around with different settings. Maybe the bin filling strategy I suggested can be improved but it's surprisingly simple and that's always a good sign: Put each object in the bin that will overflow the least otherwise put it in the emptiest bin.

Simulations indicate that bins beyond three don't contribute much, at least not for the objects in this problem. I can only speculate why this is so but my guess is that it's because of the nature of the overweight distribution. With two bins the algorithm filters out the two dominant kinds of bins and picks the best all the time. With three bins also favourable contributions (low overweight) from rarer kinds of bins are added. With four bins and beyond favourable contributions are considered that are so rare they no longer give any noticeable improvement of the average.

Also simulations show the algorithm reduces the average bin overweight by 25 to 50 percent. It's not an order of magnitude but it can still be a valuable improvement in a commersial factory setting.