ASk HN: How do I solve 2d bin packing problem if I can change the bin size?

1 point

13 years ago

I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the bins. Small rectangular shapes must be packed into larger rectangles in an optimal way. There are nesting algorithms to do this optimization where the large rectangle dimensions are inputs. However, we want to optimize the dimensions of the large rectangles.

The inputs are:

-A list of unique small rectangles. The list includes the dimensions of the small rectangles, a number that represents the rectangle’s frequency of usage relative to the other small rectangles, and the orientation (whether or not it can be rotated 90 degrees)

-The maximum number of large rectangle dimensions. And the minimum and maximum dimensions of the large rectangles.

The output is an optimized list of large rectangle dimensions.

One way to prove the validity of the result is by creating a nest of the small rectangles within the large rectangles. Here is a paper and an open source project that provides a solution to the 2d bin packing problem that we are currently using to nest. We are using the Maximal Rectangle algorithm and we vary the heuristics (typically bottom left or contact point heuristics).

http://clb.demon.fi/files/RectangleBinPack.pdf

https://github.com/juj/RectangleBinPack

How do I solve this problem?

1 comment