Greedy 1D Cutting Optimization Algorithm - Developed when I needed to cut some wood planks for the new railing in the appartment I was building.

greedy_cutting.py

from dataclasses import dataclass
from typing import List
from warnings import warn
from collections import Counter

from prettytable import PrettyTable


@dataclass
class CutPiece:
    label: str
    section: str
    length: float
    quantity: int


@dataclass
class StockMaterial:
    section: str
    length: float


@dataclass
class CutPattern:
    id: int
    section: str
    quantity: int
    waste: float
    cut_pieces: List[CutPiece]


@dataclass
class CutSummary:
    cut_patterns: List[CutPattern]
    total_utilization: str
    total_waste: float
    total_length: float


def greedy_cutting(
    cut_list: List[CutPiece], material_list: List[StockMaterial], cutting_length
) -> CutSummary:
    all_pieces = []
    for piece in cut_list:
        all_pieces += [piece] * piece.quantity

    sorted_cut_list = sorted(
        all_pieces, key=lambda x: (x.section, x.length), reverse=True
    )
    total_waste = 0.0
    total_length = sum(
        [piece.length for piece in all_pieces] + [cutting_length * len(all_pieces)]
    )
    i = 0
    all_cut_outs = []
    cut_patterns = []
    while sorted_cut_list:
        cut_outs = []
        sections = {x.section for x in sorted_cut_list}
        for section in sections:
            for stock_material in [
                stock for stock in material_list if stock.section == section
            ]:
                remaining_length = stock_material.length
                section_pieces = [
                    piece for piece in sorted_cut_list if piece.section == section
                ]
                if len(section_pieces) > 0:
                    for piece in section_pieces:
                        if piece.length > stock_material.length:
                            warn(
                                f"Length of {piece} is {piece.length} "
                                f"which is longer than the length of stock material ({stock_material.length})"
                            )
                        if piece.length <= remaining_length:
                            remaining_length -= piece.length - cutting_length
                            sorted_cut_list.remove(piece)
                            cut_outs.append(piece)
                        if remaining_length <= 0.0:
                            remaining_length = 0.0
                            break
                    total_waste += remaining_length

                else:
                    warn(f"Could not find any pieces with the section '{section}'")
        i += 1

        if cut_outs not in all_cut_outs:
            all_cut_outs.append(cut_outs)
            cut_patterns.append(
                CutPattern(
                    id=i,
                    section=cut_outs[0].section,
                    quantity=1,
                    waste=total_waste,
                    cut_pieces=cut_outs,
                )
            )
        else:
            for cut_pattern in cut_patterns:
                if cut_pattern.cut_pieces == cut_outs:
                    cut_pattern.quantity += 1

    total_utilization = 1 - total_waste / total_length
    return CutSummary(cut_patterns, total_utilization, total_waste, total_length)


if __name__ == "__main__":
    cut_list1 = [
        CutPiece(label="short", section="21x43", length=148, quantity=8),
        CutPiece(label="middle", section="21x43", length=1137, quantity=8),
        CutPiece(label="long", section="21x43", length=1924, quantity=8),
        CutPiece(label="vertical", section="21x43", length=957, quantity=24),
    ]

    material_list1 = [StockMaterial(section="21x43", length=3900)]
    
    result = greedy_cutting(cut_list1, material_list1, 5)
    print(f"Total Utilization: {result.total_utilization*100:0.1f} %")
    print(f"Total Waste: {result.total_waste}")
    print(f"Total Length: {result.total_length}")

    table = PrettyTable(["id", "section", "quantity", "waste", "cut pieces"])
    for cut_pattern in result.cut_patterns:
        pieces = Counter([piece.label for piece in cut_pattern.cut_pieces])
        table.add_row(
            [
                cut_pattern.id,
                cut_pattern.section,
                cut_pattern.quantity,
                cut_pattern.waste,
                pieces.most_common(len(pieces)),
            ]
        )
    print(table)