# on-line Batched bin Packing

I have a project concerning "on-line Batched bin Packing" where the item sizes should be between 0 and 1 and have to be packed into bins of size 1.

In my project I have to design a 3-batched online bin packing. For this version of the problem, the items to be packed arrive in at most 3 batches, and each batch contains items of only ONE size. My goal is to find goal is to find a good way to deal with the first two batches, and prove mathematically that the resulting algorithm has good performance, when compared to the optimal solution.

The second problem I am facing is to find the asymptotic competitive ratio for this kind of problem.

For example, if the input like this:

165 N * 1/1000

   N * 0.334

N * 0.501 or N*0.51


How does it pack the first batch?

How does it pack the last batch?

What is the competitive ratio?

I will appreciated if someone can help me to find a good way to deal with this.

-