2D Bin Packing Problem Solver
This online calculator tries to solve an offline twodimensional (2D) bin packing problem using Maximal Rectangles heuristic algorithm
This online calculator should help you to answer the questions like how many slabs needed, if you are fitting series of smaller rectangles of various length and width (LxW) dimensions into a larger rectangles with fixed length and width (LxW) dimensions.
For example, you are a countertop maker and need to figure out how many slabs of a certain size you need to order for a job. Thus, amount of material needed should be broken down into a series of small rectangles (see this request).
Below you should enter the dimensions of the master slab in Length x Width format, then dimensions of rectangular pieces and their quantity, in Length x Width x Quantity format, one type of rectangles per line.
In fact, this is TwoDimensional Rectangle Bin Packing problem. The calculator will try to find the best layout it can, but, unfortunately, it does not guarantee the optimal solution. For science details, refer to the theory section below the calculator.
TwoDimensional Rectangle Bin Packing
Ok, so here we deal with TwoDimensional Rectangle Bin Packing problem. In any bin packing problem, you are given some sort of containers (in our case container is a 2D rectangular region) and some set of objects (again, in our case, these are smaller rectangles), which must be packed into one or more containers. The goal usually is to pack all objects using as few containers as possible.
If the set of objects to be packed is known beforehand the problem is called 'offline' as opposite to 'online' problem, where objects appear one by one. So, here we need to deal with offline 2D rectangle bin packing problem.
This is one of classical problems in combinatorial optimization and is proven to be NPhard. So, we can only approximate the optimal solution with heuristic algorithms.
This particular implementation of 2D bin packing problem solver relies on Maximal Rectangles Algorithms. This heuristic is an extension of the Guillotine Split heuristic and shows excellent results for offline packing^{1}
The idea of the Maximal Rectangles heuristic is to keep track of all maximal free rectangular spaces, which are still available after placing object into the container (see picture below)
There are also different rules for choosing which rectangle to place into which bin. Here we use global approach, which means that on each step we compute 'score' for each remaining rectangle and for each remaining free space and choose the combination which gives us the best score. As for particular placement rule, this implementation actually checks four of them, and then picks the rule which produces the best result (f.e. uses minimum amount of bins).
The placement rules are:
 BottomLeft  the ycoordinate of the top side of the rectangle should be the smallest. In case of tie, the one with the smallest xcoordinate value is used.
 Best Shoft Side Fit  the free space area should have the minimum length of the shorter leftover side.
 Best Long Side Fit  the free space area should have the minimum length of the longer leftover side.
 Best Area Fit  the free space area should be the smallest in area to place the next rectangle into. If case of tie, the Best Short Side Fit rule is used.

A Thousand Ways to Pack the Bin  A Practical Approach to TwoDimensional Rectangle Bin Packing by Jukka Jylänki ↩
Comments