Optimaler Guillotine Zuschnitt

Aus Physik
Version vom 9. März 2010, 22:05 Uhr von Humer s (Diskussion | Beiträge)

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Wechseln zu: Navigation, Suche

Allgemeines

Schnittoptimierung ist ein großes Themengebiet mit einer breiten Anwendung. z.B. Holz, Glas, Textilindustrie. Bei reinen Rechtecksproblemen unterscheidet man Guillotine-Schnitt und Nicht-Guillotine-Schnitt. Guillot.jpg

Optimierung

Wichtig ist je nach Anwendung herauszufinden nach welchem konkrten Kriterium optimiert werden soll. In meinem Fall optimiere ich bei gegebener Breite die Länge. D.h. Die Eingabeparameter sind: Länge/Breite der kleinen Rechtecke, Breite des Stücks aus dem ausgeschnitten werden soll. Die Ausgabe ist der Verschnitt, eine grafische Schnittanweisung, die minimal mögliche Länge.

Ansatz

Der programmiertechnische Ansatz beim Guillotineschnitt ist immer zwei und zwei kleine Rechtecke „zusammenkleben“. Dafür gibt es exakt 4 Möglichkeiten.

Viermoegl.jpg

praktische Umsetzung

Bei jedem Schritt werden aus 2 kleinen Rechtecken ein Großes, wobei eine Optimierung vorgenommen wird, indem aus den 4 Möglichkeiten das kleinste ausgewählt wird und dies bei allen Kombinationsmöglichkeiten der kleinen Rechtecke. Die Randbedienung lautet dabei, nicht breiter als eine die Eingabe zu werden und nicht länger als nötig.

Beispiel

4 kleine Rechtecke werden ausgewertet nach Verschnitt bei verschiedenen Breiten. (x,y): (4.43,2.11),(8.50,3.33), (2.21,8.03), (3.55,2.70)

Verschnbr.jpg

Schn6.jpg

Schn9.jpg

Schn13.jpg

Literatur

Guntram Scheithauer; "Zuschnitt- und Packungsoptimierung"; ISBN 978-3-8351-0215-6; Vieweg + Teubner Verlag

Fritsch Andreas; "Verschnittoptimierung durch iteriertes Matching" Diplomarbeit im Studiengang Diplom Mathematik; Universität Osnabrück