The stock cutting problem
Every shop that cuts sheet or board material runs into the same question. How many parts can you get out of the stock you have, and how little of it can you throw away? A cabinet shop, a metal fabricator and a textile cutter all meet it in more or less the same form. It has been worth money for long enough that both the mathematics and the software have had decades of attention.
Understanding the Stock Cutting Problem
Section titled “Understanding the Stock Cutting Problem”The problem is easy to state. You have stock of a known size and a list of parts you need out of it. Find the cutting patterns that use the fewest sheets, or the least length, and leave the smallest remnant behind.
Stating it is the easy part. The number of possible arrangements climbs steeply with every extra part, every additional size and every constraint the shop imposes. This is the same territory as the two-dimensional bin packing problem, and it is hard for the same reason. Short of trying the arrangements, nothing proves which one is best.
Where It Gets Difficult
Section titled “Where It Gets Difficult”Three things make it awkward in practice. A single job may call for dozens of different dimensions, each with its own quantity. The material constrains the layout as well, through wood grain direction, stress patterns in metal, or weave orientation in fabric. And the tightest layout on paper is not always the one you want, once blade kerf, cutting time and the limits of the machine are taken into account.
Importance in Industry
Section titled “Importance in Industry”In industries where material is 40-60% of total cost, a 5% improvement in yield is worth having on its own terms. The waste is the second effect. Less material bought is less consumed and less sent to landfill, which customers increasingly ask about.
The third is time. A good set of patterns means fewer machine hours and less handling, because parts come off the saw in an order that suits whatever happens next.
Methodological Approaches
Section titled “Methodological Approaches”The methods fall into three groups. Production software usually contains more than one of them.
1. Heuristic Methods
Section titled “1. Heuristic Methods”A heuristic follows a sensible rule instead of searching. ‘First Fit’ puts each piece in the first space where it fits. ‘Best Fit’ looks for the tightest placement available. Neither guarantees anything, both run quickly, and in practice they often land within 5-10% of the theoretical optimum. That is close enough for a lot of real work.
2. Mathematical and Exact Methods
Section titled “2. Mathematical and Exact Methods”Integer Linear Programming (ILP) writes the cutting problem as a system of equations and constraints and hands it to a solver. When an answer arrives it is provably optimal. The difficulty is when. Solve time grows fast with the size of the instance, and a plan with 50 different pieces might take hours or even days to solve exactly.
3. Metaheuristic Algorithms
Section titled “3. Metaheuristic Algorithms”Metaheuristics search the space of possible layouts rather than building one directly. Genetic algorithms breed better cutting patterns out of a population of candidates. Simulated annealing borrows from metallurgy, accepting a worse layout early in the run so the search can climb back out of a dead end. They offer no guarantee either, but on a hard job they typically find something close to optimal in minutes rather than hours.
Software Solutions in Practice
Section titled “Software Solutions in Practice”Cutlist Evolution runs in the browser. It takes a parts list and a stock list, across several materials and thicknesses at once, and returns the layout and the cutting instructions.
SmartCut is the same optimisation engine behind a cloud API, for manufacturers and software vendors building cutting optimisation into their own systems. It is benchmarked in the open, on thousands of real production jobs, against a provable optimality bound.
Final Thoughts
Section titled “Final Thoughts”Two things have changed here, and neither of them is the mathematics. Compute got cheap enough to search the space properly. The software got usable enough that the person cutting the material never needs to know which method produced the layout.
The problem itself is as hard as it ever was. That is the argument for handing it to something that does nothing else.