Verschnittplanung

Die Verschnittplanung beschäftigt sich mit der Problematik, eine vorgegebene Länge (Planung einer Dimension), eine vorgegebene Fläche (Planung von zwei Dimensionen) oder einen vorgegebenen Raum (Planung von drei Dimensionen) in bestimmte Teilbereiche aufzuteilen. Ziel ist dabei zum einen die Einhaltung der gewünschten Abmessungen der Teilbereiche, zum anderen die Minimierung des sogenannten Verschnitts: Die verbleibenden Restbereiche sollen minimal sein, um die Verschnittkosten zu reduzieren.

Konkrete Anwendungen sind zum Beispiel:

1-dimensionale Probleme

Zuschneiden von benötigten Rohrstücken aus Standard-Rohren.

2-dimensionale Probleme

Zuschneiden von Stoffstücken aus Rohmaterial, Ausstanzen von Formblechen aus Standardblechen.

3-dimensionale Probleme

Beladen eines Frachtraums / Containers mit Paketen, Ausschneiden von Formteilen aus Rohmaterialblöcken.

Die Verschnittplanung kennt neben einer Reihe von unterschiedlichen Zieldefinitionen (Minimierung des Verschnitts, Vermeidung der Unterschreitung von gewissen Mindestgrößen der Reststücke usw.) eine Reihe von weiteren Einschränkungen bei der Lösungsfindung: Bei Stoffzuschnitten beispielsweise muß ein Muster berücksichtigt werden, bei Holzzuschnitten der Faserverlauf, bei der Frachtbeladung die Gewichtsverteilung. Diese Vorgaben haben erheblichen Einfluß auf die Lösungsqualität, weil damit z.B. die möglichen Drehungen eines Objekts auf der Fläche oder die beliebige Positionierung im Raum eingeschränkt werden.

Für die meisten 1-dimensionalen Probleme sind Algorithmen bekannt, die innerhalb vertretbarer Rechenzeiten zu optimalen Lösungen führen. Dies gilt ebenfalls für 2-dimensionale Probleme, solange diese nur einfach geformte Flächen (z.B. Rechtecke) zum Ziel haben. Für beliebig geformte Flächen (Polygone) kommt bei praktischen Problemen die Suche nach der optimalen Lösung aufgrund der erforderlichen Rechenzeit meist nicht in Betracht. In diesem Fall werden Heuristiken eingesetzt, die eine Lösung mit hinreichender Qualität liefern, die jedoch unterhalb des theoretischen Optimums liegt.