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.
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.
Ausgangsmaterial
| Profiltyp | Länge | Anzahl | ||
|---|---|---|---|---|
Teile
| Profiltyp | Länge | Anzahl | ||
|---|---|---|---|---|
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:
- 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.
- 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.
- 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 auf einem Stab platziert werden und die Schnittbreite
beträgt, ist die belegte Länge
Dabei ist die Anzahl der Teile auf dem Stab. Der Plan ist nur zulässig, wenn
gilt, wobei
die Länge des Ausgangsmaterials ist. Das Reststück wird als
berechnet.
Warum und nicht
? Die Regel
gilt, wenn ein Stab vollständig in
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:
- 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.
- 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:
Dabei ist die Länge des
-ten Teils und
die Länge des
-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:
- Teile nach absteigender oder aufsteigender Länge;
- 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
- Stab entfernen. Der Algorithmus versucht, dessen Teile auf andere bereits verwendete Stäbe zu verschieben. Gelingt dies, wird der Stab freigegeben.
- Vertauschungen. Wenn ein einfaches Verschieben nicht hilft, probiert der Algorithmus begrenzt Vertauschungen von Teilen aus und wiederholt das Entfernen.
- 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:
Dabei ist die untere Schranke für die Stabanzahl und
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 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
- 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.
- 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.
- Teile werden nicht geteilt. Jedes Teil muss vollständig auf einen Stab passen.
- 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.
- 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.
- 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.
-
Richard E. Korf. A New Algorithm for Optimal Bin Packing. AAAI 2002. Definitionen des Problems, Heuristiken und Komplexität. Artikel. ↩
-
P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 1961. Zuschnittmuster und Spaltengenerierung. Artikel. ↩
-
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. ↩
Kommentare