Created
August 5, 2019 07:06
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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