Linear cutting. One-dimensional cutting-stock problem

One-dimensional cutting of bars with profile types, limited stock, and kerf. A plan for each bar, offcuts, material utilization, and two optimization objectives.

This page exists due to the efforts of the following people:

Timur

Timur

Created: 2026-11-22 12:35:40, Last updated: 2026-11-22 14:07:58
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/11038/. Also, please do not modify any references to the original work (if any) contained in this content.

Linear cutting is the assignment of parts to bars, rebar, pipes, or other stock items of a specified length. Parts can be rearranged: what matters is not their original position in the list, but which of them should be cut from the same bar.

The calculator below creates a plan for several profile types, takes stock quantities and kerf into account, and then shows the offcut for each bar. You can delete the default values; they are only an example. Formulas and a little theory are given below the calculator.

PLANETCALC, Linear cutting of bars

Linear cutting of bars

Stock bars

Profile typeLengthQuantity
Items per page:

Parts

Profile typeLengthQuantity
Items per page:

When the primary criteria are equal, the plan with the better secondary criterion is selected.
Additional length reserved for each placed part; in the same units as the lengths in the tables.
Status
 
Stock bars used
 
Parts placed
 
Total parts
 
Length of stock used
 
Length of parts placed
 
Total kerf
 
Total offcut
 
Material utilization, %
 
Lower bound on the number of bars
 
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.

Stock, parts, and profiles

Stock is the original bar, and a part is the piece you need to obtain. The tables use the following fields:

  1. Profile type identifies the material or rolled product, such as “A500C rebar”. A part can only be placed on stock with the same profile type. Steel rebar and an aluminium pipe should not be mixed in one plan, even if their lengths happen to match.
  2. Length is the length of the stock or part. All lengths must use the same units: if metres are selected, 80 centimetres is entered as 0.8.
  3. Quantity is the number of identical items. The calculator expands it into individual parts or bars, so a row “length 3, quantity 2” means two parts of length 3.

An offcut is the part of a used bar that did not become a part and was not consumed by cutting. It may still be useful, so calling it irrecoverable waste is not always correct. Unused bars are not included in offcuts at all.

An example with two bars

Suppose we have one 12-metre bar and one 9-metre bar. We need four parts: 8, 7, 4, and 2 metres.

One complete plan looks like this:

Stock Parts Offcut
12 m 8 + 4 m 0 m
9 m 7 + 2 m 0 m

The total length of the parts is 21 metres, exactly the same as the length of stock used. Material utilization is 100%. This is the calculator's default example, but zero offcut is, of course, not promised for other input data.

Why kerf matters

Sawing turns a small amount of material into swarf. This width is called kerf. If you ignore it, a neat plan on the screen may not fit on a real bar.

The calculator uses a conservative rule: one kerf width is reserved for each part. If parts of length L_1,\ldots,L_n are placed on a bar and the kerf is k, the occupied length is

U=\sum_{i=1}^{n}L_i+nk

where n is the number of parts on the bar. The plan is feasible only when U\leq L, where L is the stock length. The offcut is calculated as

R=L-U

Why nk rather than (n-1)k? The n-1 rule works when a bar is divided completely into n pieces. But if an offcut remains after the last part, that part still has to be separated from it. To avoid a hidden exception for an exact length match, the calculator always reserves one cut per part.

For example, two 5-metre parts with a 1-metre kerf require 12 metres rather than a 10-metre bar. Such a plan needs two bars, if they are available.

What exactly is optimized

“Optimization” has two different meanings here. You can use fewer bars, or you can leave less material on the bars used. These objectives do not always coincide.

Suppose there is one 12-metre bar and two 5-metre bars, and two 3-metre parts are required:

  1. Minimum number of bars. Both parts fit on one 12-metre bar. The offcut is 6 metres, but the two shorter bars remain untouched.
  2. Minimum total offcut. Each part is placed on its own 5-metre bar. Two bars are used, but the total offcut is only 4 metres.

That is why the calculator offers a choice of objective. Minimum offcut is selected by default. When the primary criteria are equal, the secondary one is used: first total offcut or number of bars is compared, and then the other way round.

Material utilization is useful for assessing the result: it is the proportion of finished-part length in the length of stock used:

\eta=\frac{\sum_i \ell_i}{\sum_b L_b}\cdot100\%

where \ell_i is the length of the i-th part and L_b is the length of the b-th bar used. Kerf is not included in the numerator. Therefore, material utilization, the kerf share, and the offcut share add up to 100%.

Why we cannot simply promise the best plan

This is a one-dimensional cutting-stock problem, closely related to the bin packing problem. In the classical formulation, a given set of items must be packed into the minimum number of identical bins. Our problem additionally handles different stock lengths, limited quantities, and profile compatibility.

Even classical bin packing is NP-hard.1 This does not mean that an exact answer is impossible. For a small set, you can enumerate the alternatives, and large problems are solved with integer programming and cutting-pattern generation.2 But such an exact solver would require separate limits and a much more complex implementation.

The calculator uses heuristics — rules that quickly build a good plan but do not prove its optimality. The result should therefore be read as “the best plan found”, not “the best of all possible plans”.

How the algorithm works

First, the problem is separated by profile type. This is not an approximation: a part cannot move to stock of another profile anyway. Then four construction variants are run for each profile:

  1. parts in descending or ascending order of length;
  2. when opening a new bar, the shortest suitable bar first or the longest suitable bar first.

For the next part, the best-fit rule selects an open bar where the least space will remain after placement. If none is suitable, another unused bar is opened.

The resulting plans are improved locally:3

  1. Bar removal. The algorithm tries to move its parts to other bars already in use. If it succeeds, the bar is released.
  2. Swaps. If a simple move does not help, the algorithm tries a limited number of part swaps and repeats the removal.
  3. Stock replacement. If the same group of parts fits on a shorter unused bar of the same profile, the replacement is made.

All that remains is to compare the variants using the selected objective. There is no random trial and error: repeating the calculation with the same data produces the same plan.

Lower bound on the number of bars

For one profile, the total part length can be divided by the longest available stock length and rounded up:

B_0=\left\lceil\frac{\sum L_i}{L_{\max}}\right\rceil

where B_0 is the lower bound on the number of bars and L_{\max} is the maximum available stock length for this profile. The bounds for all profiles are added together.

The bound is deliberately simple: it ignores kerf, quantity limits, and inconvenient combinations of lengths. If the plan found uses exactly B_0 bars, their number is proven to be minimal. This does not prove that the offcuts are minimal.

How to read the result

The Cutting plan contains one row per bar used. The entry “8 + 4” means two parts of the corresponding lengths; their cutting order does not affect material consumption. Each row repeats the parts length, kerf allowance, offcut, and material utilization.

Summary by profile helps check how different stock types are used. Unused stock shows the remaining supply. If no complete plan is found, the Unplaced parts table lists what the algorithm could not place.

What does this mean in practice? Perhaps there really is not enough stock, or a part is longer than any suitable bar. But another case is also possible: the heuristic failed to find an existing plan. Therefore, “no complete plan was found” is not proof that cutting is impossible.

Limitations

  1. Optimality is not guaranteed. Plan feasibility and the complete length balance are checked, but not whether the result is minimal among all possible plans.
  2. Profiles are not mixed. Their names are compared exactly, including letter case. Substituting one material for another requires a separate engineering decision, not a packing rule.
  3. Parts are not divided. Each part must fit entirely on one bar.
  4. New offcuts do not automatically become stock. If you need to use them in a subsequent job, add suitable offcuts to the stock table manually.
  5. Input limits. Up to 100 stock bars and 100 parts after expanding quantities are supported, with up to six decimal places. This is a browser calculation limit, not a property of the problem.
  6. Only length is considered. Purchase cost, end trimming, clamps, minimum useful offcut, machine operation order, and cutting time are outside the model.

If width and height are given instead of length, this is a different problem. For that, there is a 2D bin packing calculator. For identical bins without profiles or a plan for each bar, the Bin packing problem and Bin packing problem 2 calculators may be useful.


  1. Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Problem definitions, heuristics, and complexity. Paper. ↩

  2. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Cutting patterns and column generation. Paper. ↩

  3. A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. An example of combining construction and local plan improvement. Paper. ↩

URL copied to clipboard
PLANETCALC, Linear cutting. One-dimensional cutting-stock problem

Comments