In diesem Artikel geht es um die programmiertechnische Umsetzung der Optimierungslogik zum Finden wirtschaftlicher Zuschnitt-Rohlängen. Der erste Teil stellt die Optimierungslogik vor.
Jetzt steht die Programmierung der Verschnittoptimierungsroutine an. Beginnend von den möglichen Schnittkombinationen, der Simplex Methode bis zur Best-Fit Auswahl und Direct-Cut Umsetzung. Komplettiert wird alles durch das Zusammenspiel mit einer Reihe von Daten: Produktionsprogramm, Zuschnitt-Aufträge, Zusammenfassungshorizont, Schnittbreite, Länge des End-/Anfangsstücks usw. und den möglichen Rohlängen-Bereich.
Im dann folgenden Beispiel zeigt die programmierte Optimierungslogik was sie alles kann.
Die Optimierungslogik
Die Optimierungslogik besteht, wie im Artikel „Wirtschaftlichere Zuschnitt-Rohlängen mit mathematischen Methoden“ beschrieben, aus verschiedenen Methoden, welche Verschnitt-Berechnungen durchführen.
- Rohlängen
- Produktionsprogramm
- Verschnittoptimierung
Die Logik führt Berechnungsergebnisse und Daten intelligent zusammen. Sie berechnet für jede der gewünschten Rohlängen den Gesamt-Verschnitt aus dem hinterlegten Produktionsprogramm über die einzelnen Zuschnitt-Aufträge. Dadurch lassen sich die Ergebnisse der Berechnungen miteinander vergleichen. Es wird möglich, die wirtschaftlichste Rohlänge zu finden.
Kernelement Verschnittoptimierung
Der Algorithmus der Verschnittoptimierung steht dabei im Mittelpunkt der wirtschaftlichen Betrachtung. Er liefert schließlich die messbare Größe für den wirtschaftlichen Erfolg:
den Gesamt-Verschnitt.
Eingangswerte der Berechnungsmethode sind die verschiedenen Zuschnitt-Aufträge des Produktionsprogramms und einer Start-Rest-Rohlänge. Als Ausgabewerte berechnet der Algorithmus die optimale Schnittfolge, die Rest-Rohlänge nach dem Zuschnitt und den Gesamt-Verschnitt.
Start über die Schnittkombinationen
Bevor der Algorithmus eine optimale Schnittfolge berechnen kann, braucht er die möglichen Schnittkombinationen der Zuschnitt-Aufträge.
Eine Methode, welche die Schnittkombinationen ermitteln kann, ist im Artikel unter „Cutting Stock Probleme mit Excel Solver lösen“ beschrieben. Sie arbeitet unter Excel und VBA.
Die Umsetzung basierte auf der Lösung eines einzelnen Optimierungsproblems. Excel ist bei dieser Aufgabenstellen nicht das idealste Werkzeug.
Schon bei 10 Zuschnitt-Längen (z. B. 1810, 1740, 1550, 1340, 900, 800, 600, 300, 200, 100 mm) und einer Rohlänge von 6 m werden ca. 20.000 Schnittkombinationen generiert. Dafür benötigt der Excel Interpreter ca. 11 Sekunden.
Hat ein Produktionsprogramm 200 Aufträge, nimmt die Berechnung für eine Rohlänge schon länger als eine halbe Stunde in Anspruch. Sollen zusätzlich noch mehrere Rohlängen untersucht werden, dauert die Berechnungen einfach zu lange.
In diesem Fall sinnvoller die Programmierung in einem Compiler mit nativem Code umzusetzen. Setzt man die gleiche Logik mit Lazarus und Freepascal um, liegt die Dauer für die 20.000 Schnittkombinationen bei 0,3 Sekunden. Das passt schon besser für diese Art von Analyse. Die Berechnungsdauer für ein Produktionsprogramm verkürzt sich auf <1 min. Das ist bestimmt noch nicht optimal, aber eine bessere Grundlage.
Die Lazarus Version nutzt den gleichen Algorithmus, ist aber objektorientiert und verwendet dynamische Arrays für die Speicherung der Kombinationen. Zuschnitt-Aufträge werden als TRequirementsList Objekt übergeben.
Eine Übersicht der Klassen der Optimierungslogik zeigt die nebenstehnde Abbildung.
Die Prozedur Calc berechnet die Schnittkombinationen und legt sie im Array Combination ab.
TWasteCombinationArray = array of array of integer;
TWasteCombination = class
private
FRequirementsList : TRequirementsList;
procedure SetRequirementsList(AValue: TRequirementsList);
procedure Add;
public
Combination : TWasteCombinationArray; //array of array of integer;
CutLength, WasteLength: array of double;
constructor Create;
procedure Clear;
procedure Calc;
function Count : integer;
procedure Output(StringGrid : TStringGrid);
procedure SaveToFile(filename : string);
published
property RequirementsList : TRequirementsList read FRequirementsList write SetRequirementsList;
end;
Simplex Methode
Mit den Schnittkombinationen als Grundlage und den Sollmengen der Zuschnitt-Aufträge berechnet die Simplex Methode die optimale Schnittfolge.
Die Simplex Methode ist schon einige Jahre alt. Dadurch gibt es eine Vielzahl von guten Erklärungen der Methode. Diese Umsetzung basiert auf einem leicht veränderten Layout aus dem Buch „Operations Research von Zimmermann/Stache, 2001, Auflage 10“.
In Lazarus ist die Methode im Objekt TWasteOptimization gekapselt. TWasteOptimization enthält die oben genannten Schnittkombinationen in der Eigenschaft WasteCombination. Ein weiterer Eingangsparameter ist die Eigenschaft RemainingBarLength, welche die Rest-Rohlänge, die am Beginn vorhanden ist, enthält.
Die Optimierung wird über die Methode Optimize aufgerufen. In dieser wird die Simplex Methode angewendet. Das Ergebnis wird in einer TCutList gespeichert.
Findet die Optimierung eine Lösung wird die Eigenschaft OptCutList befüllt. Das aktuelle Optimierungsergebnis kann auch Schritt für Schritt nachverfolgt werden. Dann müssen anstelle der Methode Optimize, die Methoden OptimizeInit und OptimizeStep aufgerufen werden. Das jeweilige Ergebnis steht in CurrCutList.
TWasteOptimization = class
private
FRequirementsList : TRequirementsList;
FCurrCutList : TCutList; //aktuelles Ergebnis des Tableaus
FOptCutList : TCutList; //Bestes Ergebnis
FRemainingBarLength : double;
FTableau : integer;
simTab,simTabNew : array of array of double;
simResX,simResY : array of integer;
pivotCol,pivotRow : integer;
function FindPivotCol: integer;
function FindPivotRow(col: integer): integer;
function GetRequirementsList: TRequirementsList;
function MyDiv(a, b: double): double;
function OptimizeTableau : integer;
procedure SetRequirementsList(AValue: TRequirementsList);
public
WasteCombination : TWasteCombination;
constructor Create;
destructor Destroy;
function RequirementsFullfilled: TRequirementsResult;
procedure Optimize;
procedure OptimizeInit;
function OptimizeStep : boolean;
procedure Output(StringGrid : TStringGrid);
procedure CalcResult;
published
property RequirementsList : TRequirementsList read GetRequirementsList write SetRequirementsList;
property OptCutList : TCutList read FOptCutList;
property CurrCutList : TCutList read FCurrCutList;
property RemainingBarLength : double read FRemainingBarLength write FRemainingBarLength;
property Tableau : integer read FTableau write FTableau;
end;
In der Prozedur Optimize wird solange OptimizeStep aufgerufen, bis die Simplex Bedingung für das Methode-Ende erreicht ist.
procedure TWasteOptimization.Optimize;
var
finished,cancel : boolean;
begin
if FRequirementsList=nil then exit;
cancel:=false;
OptimizeInit;
repeat
finished:=OptimizeStep;
if FTableau>1000 then cancel:=true; //nach 1000 Tableaus abbrechen
until (finished=true) or (cancel=true);
if cancel=true then FCurrCutList.SimplexInf.hasNoSolution:=true;
end;
Dieses Ergebnis liefert OptimizeStep als booleschen Wert. Jeder Aufruf berechnet ein Simplex Tableau.
function TWasteOptimization.OptimizeStep : boolean; begin if FRequirementsList=nil then exit; … result:=FCurrCutList.SimplexInf.isFinished; end;
Verbesserungen der Methode
Nicht bei jeder Konstellation von Zuschnitt-Aufträgen macht es Sinn die Simplex Methode einzusetzen. Handelt es sich um einen Auftrag mit einer Gesamtschnittlänge kleiner der Rohlänge, ist es unnötig die Methode einzusetzen. Es reicht den Auftrag direkt zu sägen, wie er ist. Deswegen prüft OptimizeStep das als erstes mit dem Rest-Zuschnitt.
Best-Fit Auswahl
Die Simplex Methode liefert als Ergebnis (auch) reelle Zahlen. Mein Algorithmus rundet in diesem Fall immer ganzzahlig ab. Dadurch entstehen aber Mindermengen für die Erreichung der Sollwerte des Zuschnitt-Auftrags.
Für dieses Delta von Sollmenge zu Mindermenge muss ebenfalls eine Verschnitt-optimierte Lösung gefunden werden. Ein nochmaliger Einsatz der Simplex Methode macht aber wenig Sinn, da mit der Logik abrunden und kleinen Deltas keine ganzen Schnittkombinationen gefunden werden können.
Besser ist es aus allen Schnittkombinationen diejenige zu finden, welche mindestens die Deltamengen abdecken und dabei den kleinsten Verschnitt haben. Das wird solange ausgeführt bis die Sollmengen erreicht sind oder keine weitere Schnittkombinationen mehr gefunden wird.
d2:=0;
repeat
d2:=d2+1;
waste:=MaterialData.RawLength;
d1:=0; //beste Id
for x:=1 to high(WasteCombination.Combination) do
begin
b:=true;
for y:=0 to high(FCurrCutList.Items) do
if WasteCombination.Combination[x,y+1]>FCurrCutList.Items[y].AmountDestination-FCurrCutList.Items[y].Amount then b:=false;
if b=true then
begin
if WasteCombination.WasteLength[x]<waste then
begin
d1:=x; //beste Id
waste:=WasteCombination.WasteLength[x];
end;
end;
end;
if d1>0 then
begin
bar.Amount:=1;
bar.CombinationId:=d1;
bar.WasteLength:=WasteCombination.WasteLength[bar.CombinationId]
+MaterialData.BeginLength+MaterialData.EndLength;
bar.CutLength:=WasteCombination.CutLength[bar.CombinationId];
bar.RawLength:=MaterialData.RawLength;
FCurrCutList.AddBar(bar,WasteCombination.Combination,bar.CombinationId);
end;
until (d1=0) or (d2>999);
Direct-Cut Umsetzung
Finde Best-Fit keine passenden Schnittkombinationen mehr bedeutet das: die Deltamengen sind kleiner als die Zuschnitt-Rohlänge. In diesem Fall kann alles ohne weitere Rücksicht auf Verschnitte zugeschnitten werden.
Gibt es eine Rest-Zuschnittlänge wird mit dieser begonnen. Reicht sie nicht aus, holt sich der Algorithmus die nächste Rohlänge und erzeugt dadurch wieder einen neuen Rest-Zuschnitt für den nächsten Optimierungslauf.
cut:=0;
for y:=0 to high(FCurrCutList.Items) do
for x:=1 to FCurrCutList.Items[y].AmountDestination-FCurrCutList.Items[y].Amount do
begin
if cut+FCurrCutList.Items[y].CutLength+ToolData.BladeWidth>cutBar-MaterialData.EndLength then
begin
//Länge übersteigt den aktuellen Stab
//Stab hinzufügen und neuen ganzen Stab beginnen
bar.Amount:=1;
bar.CombinationId:=-1;
bar.CutLength:=cut;
bar.RawLength:=cutBar;
bar.WasteLength:=cutBar-cut;
FCurrCutList.AddBar(bar,arr,0);
cutBar:=MaterialData.RawLength;
cut:=0;
ClearCurrCutListLength(arr);
end;
cut:=cut+FCurrCutList.Items[y].CutLength+ToolData.BladeWidth;
arr[0,y+1]:=arr[0,y+1]+1;
end;
bar.Amount:=1;
bar.CombinationId:=-2;
bar.CutLength:=cut;
bar.RawLength:=cutBar;
bar.WasteLength:=cutBar-cut+MaterialData.EndLength+MaterialData.BeginLength;
//kann Reststück wiederverwendet werden?
if cutBar-cut<MaterialData.LeftoverLength then
begin
//alles Verschnitt, da Restlänge zu klein
bar.WasteLength:=FRemainingBarLength-cut;
FCurrCutList.RemainingBarLength:=0;
end
else
begin
//kein Verschnitt, da Restlänge wiederverwendet wird
bar.WasteLength:=MaterialData.BeginLength;
FCurrCutList.RemainingBarLength:=cutBar-cut;
end;
FCurrCutList.AddBar(bar,arr,0);
end;
Produktionsprogramm und Rohlängen
Für die Anwendung des Verschnittoptimierungsalgorithmus kommt jetzt die Zusammenführung der Eingangsdaten und einer Steuerungslogik ins Spiel.
Darum kümmern sich die Klassen TOptimizationControl und TProductionProgram.
Rohlängen
Der einfachere Teil sind zweifelsfrei die Rohlängen. Sie werden nach den Möglichkeiten des eigenen Zuschnitts festgelegt. Sie hängen i. d. R. davon ab, welche Längen überhaupt eingekauft werden können.
Beispiel: 3000 mm, 3500 mm, 4000 mm, 4500 mm, 5000 mm, 5500 mm, 6000 mm
In Lazarus sind diese Rohlängen in der Klasse TOptimizationControl als Array Items gespeichert.
Produktionsprogramm
Die Klasse TProductionProgram kapselt die Methode für das Berechnen des Gesamt-Verschnitts unter Calc. Gleichzeigt ist sie auch für das Speichern der einzelnen Zuschnitt-Aufträge verantwortlich.
Daten
Die notwendigen Daten für die Optimierungslogik müssen außerhalb erzeugt und in die Objekte importiert werden. Das ist je nach Anwendungsfall sehr spezifisch: von Datenbank-Anbindungen, Excel Dokumente oder CSV-Dateien. Deswegen ist es hier nicht enthalten.
Erreichbare Ergebnisse
Spannender ist es die Optimierungslogik anhand eines Beispiels zu testen. Für das Produktionsprogramm eines Rundmaterials mit Durchmesser 60 mm soll ermittelt werden, welche Zuschnitt-Rohlänge am wirtschaftlichsten geeignet ist.
Die Zuschnitt-Aufträge für die 12 verschiedenen Zuschnittlängen sind für ein Jahr als Tabelle in der Form „Datum, Zuschnittlänge, Menge“ vorhanden.
Mögliche Zuschnitt-Rohlängen können im Bereich 3m bis 9m eingekauft und gelagert werden. Der Zuschnitt erfolgt an einer Kreissäge mit einer Sägeblattdicke von 3 mm.
Die kumulierte Zuschnittlänge beträgt insgesamt 1554,69 m. Dafür sind mindestens 1986 Schnitte notwendig. Der Zuschnitt-Spananteil für diese Mindestschnitte beträgt 3 mm x 1986 = 5958 mm.
Wirtschaftlichste Lösung
Damit sich sinnvoll vergleichen lässt, wie wirtschaftlich oder unwirtschaftlich eine Lösung ist, kennt man am besten die überhaupt wirtschaftlichste Lösung.
Das wäre in diesem Fall, wenn alle Zuschnitt-Aufträge nicht über ein Jahr gefertigt würden, sondern direkt hintereinander. Sozusagen eine Komplett-Fertigung der Jahresproduktion. Damit hätte die Optimierungslogik die größte Auswahl, um die wirtschaftlichsten Schnittfolgen zu berechnen.
Um das zu berechnen besteht das Produktionsprogramm aus jeweils nur einem Zuschnitt-Auftrag jeder Zuschnittlänge mit den Jahresbedarfen. Die Gesamt-Verschnitt werden für die Rohlängen im Bereich von 3000 bis 9000 mm in 500 mm Schritten berechnet.
Als Ergebnis wird dies ermittelt:
Wie zu erwarten war, nimmt mit steigenden Rohlänge der Verschnitt ab, da weniger Stäbe (mit Anfangs- und Endstücken) eingesetzt werden. Blendet man eine Trendlinie ein (gepunktet als Potenzkurve) sieht man eine leichte Verschnitt-Zunahme bei den Rohlängen 4000 mm und 7500 mm. Wirtschaftlicher als die Trendlinie ist die Rohlänge 5000 mm und 6000 mm.
Der Gesamt-Verschnittanteil liegt im Bereich 9% bei 3000 mm und 2% bei 9000 mm.
Variation von Zusammenfassungshorizont und Anzahl paralleler Aufträge
Mit Kenntnis der wirtschaftlichsten Lösung überhaupt, lassen sich weitere Simulationen mit verschiedenen Parametern durchführen. Besonders relevant sind der Zusammenfassungshorizont und die Anzahl der parallelen Zuschnitt-Aufträge.
Versuch 1: Zusammenfassungshorizont 1 Tag
| Versuch | Zusammenfassungshorizont [Tage] | Anzahl paralleler Aufträge [Stk] |
|---|---|---|
| Versuch 1-1 | 1 | 1 |
| Versuch 1-2 | 1 | 2 |
| Versuch 1-3 | 1 | 4 |
| Versuch 1-4 | 1 | ohne Beschränkung (hier 12) |
Wird das Produktionsprogramm auf die jeweiligen Versuchswerte angepasst und der Gesamt-Verschnitt neu mit der Optimierungslogik berechnet, ergibt sich dieses Ergebnis:
Man kann deutlich erkennen, dass die richtige Rohlänge eine entscheidende Rolle spielt. Bei den Rohlängen 5500 mm und 8000 mm lassen sich fast, unabhängig von der Anzahl möglicher paralleler Aufträge, optimale Gesamt-Verschnitte erreichen lassen. Das entspricht einem Gesamt-Verschnittanteil von 4%.
Sehr ungünstig ist die Rohlänge 5000 mm. Hier muss mit dem 6–8-fachen des optimalen Verschnittwertes gerechnet werden, was einem Gesamt-Verschnittanteil von 41% entspricht.
Es gilt hier je größer die Anzahl der parallelen Aufträge ist, desto wirtschaftlicher kann eine Rohlänge genutzt werden.
Aber schon ab 4 parallelen Aufträgen werden nahezu optimale Ergebnisse erreicht.
Versuch 2: Variation des Zusammenfassungshorizonts bei 4 parallelen Aufträgen
| Versuch | Zusammenfassungshorizont [Tage] | Anzahl paralleler Aufträge [Stk] |
|---|---|---|
| Versuch 2-1 (=1-3) | 1 | 4 |
| Versuch 2-2 | 2 | 4 |
| Versuch 2-3 | 4 | 4 |
| Versuch 2-4 | 7 | 4 |
| Versuch 2-5 | 14 | 4 |
| Versuch 2-6 | 28 | 4 |
| Versuch 2-7 | 56 | 4 |
Mit den Parametern dieser Versuchsreihe ergibt sich folgendes Ergebnis:
Auch hier sind Rohlängen von 5500 mm und 8000 mm sehr nahe an der optimalen Komplett-Fertigung. Ein größer Zusammenfassungshorizont verbessert aber an diesen beiden Punkten nicht den Gesamt-Verschnitt, sondern verschlechtert ihn leicht. Dafür werden an den bisher ungünstigen Rohlängen bessere Gesamt-Verschnitte erreicht.
Fazit
An diesem Beispiel wird deutlich, dass es Sinn macht, sich mit der Bestimmung der wirtschaftlichen Rohlänge zu beschäftigen. Bei der ungünstigsten Konstellation (Versuch 1-1) erreicht der Gesamt-Verschnittanteil bis zu 51%.
Kann die Rohlänge nicht verändert werden, sieht man auch, dass durch eine Erhöhung der Anzahl der parallelen Aufträge sich der Gesamt-Verschnitt ebenfalls reduzieren lässt. Im Versuch 1 sind das bei der Rohlänge 5000 mm bis zu 19%.
Was ebenfalls klar wird ist, dass eine optimale Schnittfolge immer die beste Basis für einen wirtschaftlichen Zuschnitt ist. Zusammen mit der richtigen Rohlänge kommt man mit fast jeder Parameterkonfiguration sehr nahe an den optimalen Gesamt-Verschnitt heran.
Download
Mehr zum Thema Verschnittoptimierung
Die Wirtschaftlichkeit beim der Verschnittoptimierung hängt von vielen Faktoren ab. Einer davon ist richtige Zuschnitt Rohlänge. Einen Vorschlag für eine Methode zum Finden dieser, beschreibt der Artikel Wirtschaftlichere Zuschnitt-Rohlängen mit mathematischen Methoden.
Mehr zum Thema Operations Research finden Sie unter hier.
