Bin Packing for Manufacturing: BFD + Local Search

The Problem

You have a list of tubes (or bars, profiles, extrusions) of various lengths, and stock material of a fixed length (e.g., 6000mm bars). You need to cut the tubes from the stock with minimal waste. This is the 1D bin packing problem — NP-hard in general, but excellent approximate solutions exist.

Real-world constraints make it harder:

• Each cut has a kerf (blade width, typically 3-5mm) that consumes material
• Manufacturing rules may require specific items to be placed first on each bar
• Items may have different cross-section shapes that can't share a bar

Phase 1: Best-Fit Decreasing (BFD)

The BFD algorithm is simple and effective:

1. Sort all items by length, longest first
2. For each item, find the fullest bar that can still fit it
3. If no bar fits, create a new bar

The key difference from First-Fit Decreasing (FFD): BFD picks the bar with the least remaining space that still fits the item, while FFD picks the first bar that fits. BFD produces tighter packing because it fills bars more completely before moving to the next.

// BFD: Pick the FULLEST bar that can fit this tube
var targetBar = bars
    .Where(b => b.CanFit(tube.Length))
    .OrderBy(b => b.RemainingLength) // Smallest gap first
    .FirstOrDefault();

Phase 2: Local Search Improvement

BFD gives a good initial solution, but it can often be improved by moving items between bars:

for each tube on each bar:
    for each other bar that can fit this tube:
        temporarily move the tube
        if this eliminates an empty bar:
            accept the move
        else:
            revert the move

This iterates until no more improvements are found. Typically converges in 50-200 iterations, taking under 100ms.

The acceptance criterion is simple: only accept moves that reduce the total number of bars. More sophisticated criteria (minimizing max waste, balancing load) are possible but rarely worth the complexity.

Phase 3: Constraint Redistribution

Manufacturing often imposes domain-specific constraints. For example, in tube cutting:

• The first tube on each bar must be hex-free (no hexagonal holes) because the machine's clamping system can't grip hex-punched tubes
• Certain material grades can't be mixed on the same bar

After the optimization phases, redistribute items to satisfy these constraints without increasing bar count:

1. Identify bars that violate constraints
2. Find compliant items on other bars that can swap in
3. Perform swaps or moves to fix violations
4. Warn the user if constraints can't be satisfied

Implementation Structure

public NestingResult Optimize(List<TubeSpec> specs)
{
    // Expand quantities into individual instances
    var expanded = specs.SelectMany(s =>
        Enumerable.Range(0, s.Quantity)
            .Select(_ => s.Clone())).ToList();

    // Group by shape (can't mix shapes on a bar)
    var groups = expanded.GroupBy(t => t.Shape);

    foreach (var group in groups)
    {
        var bars = BFD(group.ToList());
        bars = LocalSearch(bars);
        RedistributeForConstraints(bars);
        result.BarsByShape[group.Key] = bars;
    }
}

Algorithm Comparison

For manufacturing, BFD + Local Search hits the sweet spot: close to optimal results with sub-second runtime. The 3-8% waste range is acceptable for most shops — the cost of the algorithm running a few seconds longer is negligible compared to material savings.

Performance

Typical manufacturing batches (50-200 items, 10-30 bars) solve in 100-300ms. The local search phase dominates runtime but converges quickly because each iteration eliminates a bar (finite improvements).

For very large batches (1000+ items), consider limiting local search iterations with a maxIterations parameter (2000 is a good default).