Linearer Zuschnitt. Eindimensionales Zuschnittproblem

Eindimensionaler Zuschnitt von Stäben mit Profiltypen, begrenztem Ausgangsmaterial und Schnittbreite. Plan für jeden Stab, Reststücke, Materialausnutzung und zwei Optimierungsziele.

Diese Webseite exisiert dank der Arbeit von den folgenden Menschen:

Timur

Timur

Erstellt: 2026-11-22 12:35:44, Letzte Aktualisierung: 2026-11-22 14:08:02
Creative Commons Attribution/Share-Alike License 3.0 (Unported)

Der Inhalt ist unter der Creative Commons Namensnennung / Weitergabe unter gleichen Bedingungen 3.0 (nicht portiert) lizenziert. Dies bedeutet, dass Sie diesen Inhalt unter den gleichen Lizenzbedingungen frei weitergeben oder ändern dürfen, jedoch mit Zuordnung zum Entwickler indem Sie einen Hyperlink auf Ihrer Webseite zu dieser Arbeit https://de.planetcalc.com/11038/ platzieren. Des Weiteren ändern Sie bitte keine Verweise auf das Originalwerk (falls vorhanden) das in diesem Inhlat vorhanden ist.

Linearer Zuschnitt ist die Verteilung von Teilen auf Stäbe, Bewehrungsstahl, Rohre oder anderes Ausgangsmaterial mit vorgegebener Länge. Die Teile dürfen vertauscht werden: Entscheidend ist nicht ihre ursprüngliche Position in der Liste, sondern welche Teile aus demselben Stab geschnitten werden sollten.

Der Rechner unten erstellt einen Plan für mehrere Profiltypen, berücksichtigt die verfügbaren Mengen und die Schnittbreite und zeigt anschließend das Reststück jedes Stabs. Die Standardwerte können gelöscht werden; sie dienen nur als Beispiel. Formeln und etwas Theorie finden Sie unter dem Rechner.

PLANETCALC, Linearer Zuschnitt von Stäben

Linearer Zuschnitt von Stäben

Ausgangsmaterial

ProfiltypLängeAnzahl
Elemente pro Seite:

Teile

ProfiltypLängeAnzahl
Elemente pro Seite:

Bei Gleichstand des Hauptkriteriums wird der Plan mit dem besseren zweiten Kriterium gewählt.
Zusätzliche Länge, die für jedes platzierte Teil reserviert wird; in derselben Einheit wie die Längen in den Tabellen.
Status
 
Verwendete Stäbe
 
Platzierte Teile
 
Teile insgesamt
 
Länge des verwendeten Ausgangsmaterials
 
Länge der platzierten Teile
 
Gesamte Schnittbreite
 
Restmaterial insgesamt
 
Materialausnutzung, %
 
Untere Schranke für die Stabanzahl
 
Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.
Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.
Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.
Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.

Ausgangsmaterial, Teile und Profile

Ausgangsmaterial ist der ursprüngliche Stab, ein Teil ist das Stück, das Sie erhalten möchten. In den Tabellen werden folgende Felder verwendet:

  1. Profiltyp bezeichnet das Material oder Walzprodukt, zum Beispiel „Bewehrungsstahl A500C“. Ein Teil kann nur auf Ausgangsmaterial mit demselben Profiltyp platziert werden. Bewehrungsstahl und ein Aluminiumrohr sollten nicht in einem Plan gemischt werden, selbst wenn ihre Längen zufällig zusammenpassen.
  2. Länge ist die Länge des Ausgangsmaterials oder Teils. Alle Längen müssen dieselbe Einheit verwenden: Bei Metern werden 80 Zentimeter als 0,8 eingegeben.
  3. Anzahl ist die Zahl gleicher Positionen. Der Rechner löst sie in einzelne Teile oder Stäbe auf; eine Zeile „Länge 3, Anzahl 2“ bedeutet also zwei Teile der Länge 3.

Ein Reststück ist der Teil eines verwendeten Stabs, der weder zu einem fertigen Teil wurde noch beim Schneiden verbraucht wurde. Es kann noch verwendbar sein; daher ist es nicht immer richtig, es als unvermeidbaren Abfall zu bezeichnen. Nicht verwendete Stäbe zählen überhaupt nicht zum Restmaterial.

Ein Beispiel mit zwei Stäben

Angenommen, wir haben einen 12-Meter-Stab und einen 9-Meter-Stab. Benötigt werden vier Teile: 8, 7, 4 und 2 Meter.

Ein vollständiger Plan sieht so aus:

Ausgangsmaterial Teile Reststück
12 m 8 + 4 m 0 m
9 m 7 + 2 m 0 m

Die Gesamtlänge der Teile beträgt 21 Meter, genauso viel wie die Länge des verwendeten Ausgangsmaterials. Die Materialausnutzung beträgt 100%. Dies ist das Standardbeispiel des Rechners; für andere Eingabedaten ist ein Reststück von null natürlich nicht garantiert.

Warum die Schnittbreite wichtig ist

Beim Sägen wird ein kleiner Teil des Materials zu Spänen. Diese Breite heißt Schnittbreite (kerf). Wenn man sie ignoriert, passt ein schöner Plan auf dem Bildschirm möglicherweise nicht auf einen realen Stab.

Der Rechner verwendet eine konservative Regel: Für jedes Teil wird eine Schnittbreite reserviert. Wenn Teile der Länge L_1,\ldots,L_n auf einem Stab platziert werden und die Schnittbreite k beträgt, ist die belegte Länge

U=\sum_{i=1}^{n}L_i+nk

Dabei ist n die Anzahl der Teile auf dem Stab. Der Plan ist nur zulässig, wenn U\leq L gilt, wobei L die Länge des Ausgangsmaterials ist. Das Reststück wird als

R=L-U

berechnet.

Warum nk und nicht (n-1)k? Die Regel n-1 gilt, wenn ein Stab vollständig in n Stücke geteilt wird. Bleibt nach dem letzten Teil jedoch ein Reststück, muss dieses Teil noch davon abgetrennt werden. Um keine versteckte Ausnahme für eine exakte Längenübereinstimmung zu machen, reserviert der Rechner immer einen Schnitt pro Teil.

Zwei Teile von je 5 Metern mit einer Schnittbreite von 1 Meter benötigen beispielsweise 12 Meter statt eines 10-Meter-Stabs. Für diesen Plan werden zwei Stäbe benötigt, sofern vorhanden.

Was genau optimiert wird

„Optimierung“ hat hier zwei verschiedene Bedeutungen. Man kann weniger Stäbe verbrauchen oder auf den verwendeten Stäben weniger Material übrig lassen. Diese Ziele stimmen nicht immer überein.

Angenommen, es gibt einen 12-Meter-Stab und zwei 5-Meter-Stäbe, benötigt werden zwei Teile von je 3 Metern:

  1. Minimale Stabanzahl. Beide Teile passen auf einen 12-Meter-Stab. Das Reststück beträgt 6 Meter, dafür bleiben die beiden kürzeren Stäbe unangetastet.
  2. Minimales Restmaterial insgesamt. Jedes Teil wird auf einem eigenen 5-Meter-Stab platziert. Zwei Stäbe werden verwendet, aber das gesamte Restmaterial beträgt nur 4 Meter.

Deshalb kann im Rechner das Ziel gewählt werden. Standardmäßig ist minimales Restmaterial ausgewählt. Bei Gleichstand des Hauptkriteriums wird das zweite Kriterium verwendet: Zuerst werden Restmaterial oder Stabanzahl verglichen, danach umgekehrt.

Zur Bewertung des Ergebnisses ist die Materialausnutzung nützlich — der Anteil der Länge fertiger Teile an der Länge des verwendeten Ausgangsmaterials:

\eta=\frac{\sum_i \ell_i}{\sum_b L_b}\cdot100\%

Dabei ist \ell_i die Länge des i-ten Teils und L_b die Länge des b-ten verwendeten Stabs. Die Schnittbreite geht nicht in den Zähler ein. Daher ergeben Materialausnutzung, Anteil der Schnitte und Anteil der Reststücke zusammen 100%.

Warum man nicht einfach den besten Plan versprechen kann

Dies ist ein eindimensionales Zuschnittproblem (one-dimensional cutting-stock problem), eng verwandt mit dem Bin-Packing-Problem. In der klassischen Formulierung muss eine gegebene Menge von Objekten in die kleinstmögliche Anzahl gleicher Behälter gepackt werden. Unsere Aufgabe berücksichtigt zusätzlich unterschiedliche Längen des Ausgangsmaterials, begrenzte Mengen und kompatible Profile.

Schon das klassische Bin Packing ist NP-schwer.1 Das bedeutet nicht, dass eine exakte Antwort unmöglich ist. Bei einer kleinen Menge können Varianten aufgezählt werden; große Aufgaben löst man mit ganzzahliger Programmierung und der Erzeugung von Zuschnittmustern.2 Ein solcher exakter Löser würde jedoch eigene Beschränkungen und eine deutlich komplexere Implementierung erfordern.

Der Rechner verwendet Heuristiken — Regeln, die schnell einen guten Plan erstellen, aber seine Optimalität nicht beweisen. Das Ergebnis sollte daher als „bester gefundener Plan“ und nicht als „bester aller möglichen Pläne“ gelesen werden.

Wie der Algorithmus arbeitet

Zuerst wird die Aufgabe nach Profiltypen getrennt. Das ist keine Näherung: Ein Teil kann ohnehin nicht auf Ausgangsmaterial eines anderen Profils verschoben werden. Anschließend werden für jedes Profil vier Konstruktionsvarianten ausgeführt:

  1. Teile nach absteigender oder aufsteigender Länge;
  2. beim Öffnen eines neuen Stabs zuerst der kürzeste oder zuerst der längste passende Stab.

Für das nächste Teil wählt die Best-Fit-Regel den bereits geöffneten Stab, auf dem nach der Platzierung am wenigsten Platz übrig bleibt. Passt keiner, wird ein weiterer unbenutzter Stab geöffnet.

Die erhaltenen Pläne werden lokal verbessert:3

  1. Stab entfernen. Der Algorithmus versucht, dessen Teile auf andere bereits verwendete Stäbe zu verschieben. Gelingt dies, wird der Stab freigegeben.
  2. Vertauschungen. Wenn ein einfaches Verschieben nicht hilft, probiert der Algorithmus begrenzt Vertauschungen von Teilen aus und wiederholt das Entfernen.
  3. Ausgangsmaterial ersetzen. Passt dieselbe Teilegruppe auf einen kürzeren unbenutzten Stab desselben Profils, wird der Stab ersetzt.

Schließlich werden die Varianten nach dem gewählten Ziel verglichen. Zufälliges Probieren gibt es hier nicht: Eine wiederholte Berechnung mit denselben Daten ergibt denselben Plan.

Untere Schranke für die Stabanzahl

Für ein Profil kann die Gesamtlänge der Teile durch die längste verfügbare Materiallänge geteilt und aufgerundet werden:

B_0=\left\lceil\frac{\sum L_i}{L_{\max}}\right\rceil

Dabei ist B_0 die untere Schranke für die Stabanzahl und L_{\max} die maximal verfügbare Materiallänge für dieses Profil. Die Schranken der Profile werden addiert.

Die Schranke ist absichtlich einfach: Sie berücksichtigt weder Schnittbreite noch Mengenbegrenzungen oder ungünstige Längenkombinationen. Verwendet der gefundene Plan genau B_0 Stäbe, ist ihre Anzahl nachweislich minimal. Daraus folgt nicht, dass auch die Reststücke minimal sind.

Wie das Ergebnis zu lesen ist

Der Zuschnittplan enthält eine Zeile pro verwendetem Stab. Der Eintrag „8 + 4“ bedeutet zwei Teile mit den entsprechenden Längen; ihre Schnittreihenfolge beeinflusst den Materialverbrauch nicht. In jeder Zeile werden Teilelänge, Schnittreserve, Reststück und Materialausnutzung erneut angezeigt.

Die Zusammenfassung nach Profilen hilft, die Verteilung auf die Materialtypen zu prüfen. Nicht verwendetes Ausgangsmaterial zeigt den verbleibenden Bestand. Wenn kein vollständiger Plan gefunden wird, listet die Tabelle Nicht platzierte Teile auf, was der Algorithmus nicht platzieren konnte.

Was bedeutet das in der Praxis? Möglicherweise reicht das Ausgangsmaterial tatsächlich nicht aus oder ein Teil ist länger als jeder passende Stab. Es ist aber auch möglich, dass die Heuristik einen vorhandenen Plan nicht gefunden hat. „Kein vollständiger Plan gefunden“ beweist daher nicht, dass kein Zuschnitt möglich ist.

Grenzen der Anwendung

  1. Optimalität wird nicht garantiert. Geprüft werden die Zulässigkeit des Plans und die vollständige Längenbilanz, nicht aber, ob das Ergebnis unter allen möglichen Plänen minimal ist.
  2. Profile werden nicht gemischt. Ihre Namen werden exakt verglichen, einschließlich Groß- und Kleinschreibung. Ein Material durch ein anderes zu ersetzen erfordert eine separate technische Entscheidung, keine Packungsregel.
  3. Teile werden nicht geteilt. Jedes Teil muss vollständig auf einen Stab passen.
  4. Neue Reststücke werden nicht automatisch zu Ausgangsmaterial. Wenn sie in einer späteren Arbeit verwendet werden sollen, fügen Sie geeignete Reststücke manuell zur Tabelle des Ausgangsmaterials hinzu.
  5. Eingabegrenzen. Nach dem Ausmultiplizieren der Anzahlen werden bis zu 100 Stäbe und 100 Teile mit höchstens sechs Nachkommastellen unterstützt. Dies ist eine Grenze der Browserberechnung, keine Eigenschaft des Problems.
  6. Nur die Länge wird berücksichtigt. Einkaufskosten, Endbeschnitt, Spannvorrichtungen, kleinstes brauchbares Reststück, Arbeitsreihenfolge der Maschine und Schnittzeit sind nicht Teil des Modells.

Wenn statt einer Länge Breite und Höhe von Rechtecken angegeben sind, handelt es sich um eine andere Aufgabe. Dafür gibt es den Rechner für zweidimensionales Bin Packing. Für gleiche Behälter ohne Profile und ohne Plan für jeden Stab können die Rechner Bin-Packing-Problem und Bin-Packing-Problem 2 nützlich sein.


  1. Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Definitionen des Problems, Heuristiken und Komplexität. Artikel. ↩

  2. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Zuschnittmuster und Spaltengenerierung. Artikel. ↩

  3. A. C. F. Alvim, C. C. Ribeiro, F. Glover, D. J. Aloise. A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 2004. Ein Beispiel für die Kombination von Konstruktion und lokaler Planverbesserung. Artikel. ↩

URL zum Clipboard kopiert
PLANETCALC, Linearer Zuschnitt. Eindimensionales Zuschnittproblem

Kommentare