Cutting Fabric & Metal Rolls
Cutting Stock Problem
A manufacturer must cut standard-length stock rolls into pieces of varying lengths to fulfill customer orders. Each order type specifies a required length and a demand quantity. The goal is to minimize the number of rolls used — and thereby minimize material waste. This is the 1D Cutting Stock Problem, a fundamental challenge in Operations Research with direct impact on manufacturing costs.
The Problem
Minimizing waste in industrial cutting operations
Consider a fabric or steel mill that stocks raw material in rolls of a fixed length L. Customer orders arrive specifying m item types, each with a required piece length li and a demand quantity di. The task is to cut stock rolls into pieces that satisfy every order while using the fewest rolls possible. Any leftover material on a roll after cutting is wasted trim loss.
The Cutting Stock Problem generalizes Bin Packing — identical items are interchangeable, so we think in terms of cutting patterns (how many of each item type to cut from a single roll) rather than individual piece assignments. Even so, the problem is NP-hard, meaning no known algorithm can guarantee an optimal solution in polynomial time. For real-world instances with dozens of item types and demands in the hundreds, heuristic approaches are essential.
In practice, even a 1–2% reduction in waste can translate to substantial annual savings for industries cutting fabric, paper, sheet metal, glass, cable, or timber. The problem was first studied systematically by Gilmore & Gomory (1961), who introduced a column generation approach that remains the gold standard for large-scale instances.
subject to
Σj aij · yj ≥ di // demand for item type i satisfied
Σi li · aij ≤ L // pattern j fits within roll length
aij ≥ 0, integer // count of item i in pattern j
yj ≥ 0, integer // number of rolls cut with pattern j
Try It Yourself
Optimize cutting patterns to minimize roll usage
Roll Cutting Optimizer
L=100 · 4 Types · 14 Items| Name | Length | Demand |
|---|
| Algorithm | Rolls Used | Total Waste | Waste % | Time |
|---|
Configure orders and click Solve & Compare All Algorithms to begin.
The Algorithms
Heuristic approaches for cutting stock optimization
Greedy Largest-First
Expand all demands into individual items (e.g., Type A with demand 3 becomes three separate items of that length). Sort all items by length in descending order. For each item, scan existing rolls and place it on the first roll with enough remaining capacity. If no roll can fit the item, open a new roll. This is essentially First Fit Decreasing (FFD) applied to the expanded item list.
- Expand demands: Type A (length=45, demand=3) becomes [45, 45, 45]
- Sort all expanded items descending by length
- For each item, place on first roll with sufficient remaining space
- Open a new roll only when no existing roll can accommodate the item
- Time complexity: O(N log N + N · R) where N = total items, R = rolls used
FFD-Based
Same algorithmic core as Greedy Largest-First — expand demands to individual items, sort descending by length, apply First Fit Decreasing. The key difference is in post-processing: after packing, the result is aggregated back into cutting patterns showing how many of each item type appear on each roll. This pattern view is more useful for manufacturing, where a cutting machine repeats the same pattern across multiple rolls.
- Same FFD placement logic as Greedy Largest-First
- After placement, aggregate items on each roll by type to form patterns
- Patterns show (e.g.) "2 × Type A + 1 × Type C" per roll
- Identical patterns can be grouped for batch cutting instructions
- Approximation guarantee: at most 11/9 · OPT + 6/9 rolls
Why It's More Complex
Real-world extensions beyond 1D cutting
Industrial Complications
- 2D cutting — sheet metal, glass panels, and plywood require two-dimensional nesting with irregular shapes and guillotine cuts
- Multiple stock sizes — rolls or sheets may come in different standard lengths or widths, each with its own cost per unit
- Pattern-based column generation (Gilmore-Gomory) — the LP relaxation has exponentially many variables; only promising patterns are generated on demand
- Setup costs between patterns — changing the cutting configuration on a machine incurs time and cost, favoring fewer distinct patterns
- Material grain direction — wood and fabric must be cut along the grain, constraining piece orientation
- Quality zones on rolls — defects, color variations, or thickness changes mean certain regions of the roll are unsuitable for specific orders
Key References
Foundational literature on cutting and packing
- (1961). "A linear programming approach to the cutting-stock problem." Operations Research, 9(6), 849–859.
- (2007). "An improved typology of cutting and packing problems." European Journal of Operational Research, 183(3), 1109–1130.
Need to minimize material waste?
Cutting stock optimization can reduce trim loss by 5–15% in fabric, paper, metal, and cable industries. Let's discuss how Operations Research can improve your cutting operations.