What is Bin Packing?

The bin packing problem is the mathematical challenge at the heart of every cut list optimizer. The concept is straightforward: given a set of items of different sizes and a set of fixed-size containers (bins), pack the items into the fewest bins possible.

In cutting optimization, the "items" are your parts and the "bins" are your sheets of plywood. The goal: fit every piece onto the fewest sheets.

Why it is hard. Bin packing is classified as NP-hard in computer science, which means no known algorithm can solve all instances perfectly in a reasonable time. For small projects (under 20 pieces), exact solutions are possible. For larger projects, heuristic algorithms find near-optimal solutions quickly.

Common algorithms: - First Fit Decreasing (FFD): sort parts largest to smallest, place each on the first sheet where it fits - Best Fit Decreasing (BFD): place each part on the sheet where it fits with the least leftover space - Genetic algorithms and simulated annealing: explore a much larger solution space for better results at the cost of computation time

Three dimensional variants. 1D covers cutting bars or pipes to length. 2D covers cutting sheets, which is the woodworking use case. 3D covers packing boxes into containers. Woodworking cut list optimization is a 2D bin packing problem with additional constraints like kerf width, grain direction, and guillotine-cut requirements.

This is why different optimizers give different results on the same project. They use different algorithms with different trade-offs between speed and layout quality. SmartCutList uses advanced heuristics to find near-optimal layouts in seconds.