Skip to content

Instantly share code, notes, and snippets.

@MarlevPy
Created August 5, 2019 07:06
Show Gist options
  • Save MarlevPy/d21d73be73914049e80b675d9c8b1d5e to your computer and use it in GitHub Desktop.
Save MarlevPy/d21d73be73914049e80b675d9c8b1d5e to your computer and use it in GitHub Desktop.
Greedy 1D Cutting Optimization Algorithm - Developed when I needed to cut some wood planks for the new railing in the appartment I was building.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment