Cutting Stock Probleme mit Excel Solver lösen

Themen wie Digital Workplace, Remotework, VPN und Homeoffice haben in den letzten Jahren in Firmen dominiert. Aber diese werden in der Zukunft durch andere Hotspot Themen wieder abgelöst werden. Was aber konstant bleibt: kontinuierlich an Verbesserungen zu arbeiten. Das gilt besonders in Zeiten knapper und teurer Ressourcen. Damit beschäftigt sich Operations Research.

Wikipedia beschreibt es als „Zusammenarbeit von Angewandter Mathematik, Wirtschaftswissenschaften und Informatik“ – also perfekt passend als Thema für diesen Blog.

Eindimensionales Verschnittproblem – Cutting Stock Problem

Eine Standard Aufgabe im Operations Research bildet das eindimensionale Verschnittproblem (engl. cutting stock problem). Vor diesem Problem stehen alle Firmen, die aus Rohr-/Rundmaterial Stäben verschiedene Zuschnitte herstellen. Je nach gewählter Schnittfolge entstehen prozessbedingt Rest- und Abfallstücke, die mit über den wirtschaftlichen Erfolg entscheiden. Je geringer der Verschnitt, desto mehr Material lässt sich produktiv nutzen.

Beispiel eines eindimensionalen Verschnittproblems

Operations Research hilft mit Algorithmen dabei dieses Verschnitt Potenzial zu heben und mit dem Ergebnis dadurch – mathematisch optimiert – Kosten und Ressourcen zu sparen.

Die ersten Methoden, das Problem mathematisch zu lösen, gehen auf die Simplex Methode von George Dantzig aus dem Jahr 1947 zurück. Trotz dieser langen Zeit wird dieses Potenzial in Firmen nicht immer konsequent genutzt.

Das mag damit zusammenhängen, dass die Methode sinnvoll nur mit Algorithmen und Coding genutzt werden kann.

Eine Lösung ist aber auch mit der Standardsoftware Microsoft Excel möglich. Sie bietet mit dem Solver eine gute Möglichkeit an, diese Optimierungsmethode zu nutzen.

In diesem Artikel erfahren Sie, wie Sie das konkret selber für Ihre Verschnittprobleme ausnutzen können.

Schnittkombinationen berechnen

Um eine Lösung mit der Simplex Methode berechnen zu können, müssen die Zusammenhänge des Sägeauftrages in ein mathematisches Modell überführt werden. Nur so kann eine optimale Lösung berechnet werden.

Die Simplex Methode löst ein mathematisches Maximierungsproblem. Im Fall der Verschnittoptimierung liegt aber erst mal ein Minimierungsproblem vor. Der Verschnitt soll möglichst klein gehalten werden. Im Operations Reseach spricht man deshalb von Dualität. Zu jedem Minimierungsproblem gibt es auch ein zugehöriges Maximierungsproblem, das gelöst werden kann. Hier ist das Maximierungsproblem, die größtmögliche Sägelänge eines Stabes zu erreichen.

Um zu berechnen, welche Schnittfolgen eine maximale Sägelänge erzeugen, benötigt die Simplex Methode alle sinnvollen Schnittfolgen, die mit den geforderten einzelnen Sägelängen aus einem Stab gesägt werden können.

Das lässt sich für kurze Sägeaufträge noch per Hand ermitteln, ist aber für größere Aufträge kaum mehr möglich.

Hier hilft nur Coding, das diese Arbeit zuverlässig abnimmt.

Einen Algorithmus aufbauen

Es gibt einen nicht zu unterschätzenden Vorteil, eine so alte Methode einzusetzen: Irgendjemand hat sich bestimmt bereits mit genau diesem Thema auseinandergesetzt und eine Lösung dafür gefunden.

Ich habe zwar keine fertige Routine im Internet gefunden, aber im Buch Operations Research von Zimmermann/Stache ist auf Seite 81 ein Flussdiagramm zur Ermittlung aller Schnittkombinationen abgedruckt.

Flußdiagramm eindimensionalen Verschnittproblemen / cutting stock problem — Flußdiagramm zur Ermittlung aller Schnittkombinationen bei eindimensionalen Verschnittproblemen / cutting stock problem

Der Algorithmus verlangt als Eingangsvariablen nur die geforderten Sägelängen. Außerdem müssen eine nutzbare Länge und die Schnittbreite angegeben werden. Die Daten lassen sich im Tabellenblatt „Grunddaten“ eintragen.

Als Ergebnis gibt die Routine alle möglichen Schnittkombinationen daraus zurück. Verschnitt und gesamte Sägelänge werden ebenfalls berechnet.

Umsetzung in Excel VBA

Die Umsetzung in Excel VBA sieht bei mir folgendermaßen aus:

Option Explicit

Const MAX_ITEMS = 20 'max Anzahl Sägelängen
Const MAX_COMBINATIONS = 100000 'max. mögliche Kombinationen, Excelzeilen enden bei 1.048.576

Const COL_START = 8 'Startspalte des Sägeauftrags
Const ROW_START = 7 'Startzeile der Schnittkombinationen
Const SN_COMB = "Schnittkombinationen" 'Tabellenblattname der Schnittkombinationenvorlage

Global combination(MAX_COMBINATIONS, MAX_ITEMS) As Integer
Global itemsCount As Integer
Global cutLength(MAX_ITEMS) As Double
Global wasteLength(MAX_COMBINATIONS) As Double
Global cuttedLength(MAX_COMBINATIONS) As Double
Global amountGoal(MAX_ITEMS) As Integer


'Schnittkombinationen auf dem Arbeitsblatt SN_COMB erzeugen
'und Daten für den Excel Solver vorbereiten
Sub CreateWasteCombinations()
Dim i, ii As Integer
Dim j, jj As Integer
Dim imax As Integer
Dim rr As Integer
Dim R(MAX_ITEMS) As Double
Dim sum As Double
Dim Rest As Double
Dim Verb As Double
Dim isTrue As Boolean
Dim Lblade As Double
Dim col As Integer
Dim colMax(MAX_ITEMS) As Long
Dim colMaxPieces(MAX_ITEMS) As Integer
Dim coli(MAX_ITEMS) As Integer
Dim finished As Boolean
Dim rawLength As Double
Dim s As String

  Application.ScreenUpdating = False
  
  'vorherige Daten löschen
  Sheets(SN_COMB).Rows("7:1048576").ClearContents
   
  'Grunddaten einlesen
  rawLength = Range("Grunddaten!Ln")
  Lblade = Range("Grunddaten!LSchnittbreite")
  
  'Anzahl Spalten und Grunddaten ermitteln
  itemsCount = 0
  Do
    itemsCount = itemsCount + 1
    cutLength(itemsCount) = Sheets(SN_COMB).Cells(1, COL_START + itemsCount - 1) + Lblade
    colMaxPieces(itemsCount) = Int(rawLength / (cutLength(itemsCount) + Lblade))
    amountGoal(itemsCount) = Sheets(SN_COMB).Cells(2, COL_START + itemsCount - 1)
  Loop Until Sheets(SN_COMB).Cells(1, COL_START + itemsCount) = ""
  
  'Schnittkombinationen ermitteln
  'Umsetzung der Routine von Zimmermann/Stache aus "Operations Research", 2001, Auflage 10, Seite 81
  For j = 1 To itemsCount
    R(j) = 0
  Next
  R(0) = rawLength
  
  i = 1
  j = 1
  finished = False
  combination(i, j) = Int(R(j - 1) / cutLength(j))
  Do  
    sum = 0
    For jj = 1 To itemsCount
      sum = sum + combination(i, jj) * cutLength(jj)
    Next
    R(j) = rawLength - sum
    
    If R(j) < cutLength(itemsCount) Then
    
      For jj = j + 1 To itemsCount
        combination(i, jj) = 0
      Next
      
      wasteLength(i) = R(j)
      Verb = rawLength - R(j)
      
      isTrue = True
      For jj = 1 To itemsCount - 1
        If combination(i, jj) <> 0 Then
          isTrue = False
          Exit For
        End If
      Next
      If combination(i, itemsCount) = 0 Then
        isTrue = False
      End If
              
      If isTrue = True Then
        finished = True
      Else
        Sheets(SN_COMB).Cells(i + ROW_START - 1, 1) = i
        Sheets(SN_COMB).Cells(i + ROW_START - 1, 2) = Verb
        Sheets(SN_COMB).Cells(i + ROW_START - 1, 3) = wasteLength(i)
        cuttedLength(i) = Verb
        For jj = 1 To itemsCount
          Sheets(SN_COMB).Cells(i + ROW_START - 1, COL_START - 1 + jj) = combination(i, jj)
        Next
        
        i = i + 1
        For jj = 1 To itemsCount
          combination(i, jj) = 0
          R(jj) = 0
        Next
        R(0) = rawLength
        rr = itemsCount - 1
        
        Do
          If combination(i - 1, rr) = 0 Then
            rr = rr - 1
          End If
        Loop Until combination(i - 1, rr) <> 0 Or rr <= 1
                
        For jj = 1 To rr - 1
          combination(i, jj) = combination(i - 1, jj)
        Next
        
        combination(i, rr) = combination(i - 1, rr) - 1
        j = rr
      End If
    Else
      j = j + 1
      combination(i, j) = Int(R(j - 1) / cutLength(j))
    End If
  
  Loop Until finished = True    
  imax = i
        
  'Ausgabe der letzten Zeile
  Rest = rawLength - Verb
  Sheets(SN_COMB).Cells(i + ROW_START - 1, 1) = i
  Sheets(SN_COMB).Cells(i + ROW_START - 1, 2) = Verb
  Sheets(SN_COMB).Cells(i + ROW_START - 1, 3) = Rest
  For j = 1 To itemsCount
    Sheets(SN_COMB).Cells(i + ROW_START - 1, COL_START - 1 + j) = combination(i, j)
  Next
  cuttedLength(i) = Verb
  wasteLength(i) = Rest
  
  'Formeln einfügen für den Excel Solver:
  'z berechnen
  Sheets(SN_COMB).Cells(4, 2).FormulaLocal = "=SUMMENPRODUKT(" & _
    Sheets(SN_COMB).Cells(ROW_START, 4).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 4).Address & ";" & _
    Sheets(SN_COMB).Cells(ROW_START, 2).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 2).Address & ")"
  
  For i = 1 To itemsCount
    'reele Zahlen
    Sheets(SN_COMB).Cells(3, i + COL_START - 1).FormulaLocal = "=SUMMENPRODUKT(" & _
      Sheets(SN_COMB).Cells(ROW_START, 4).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 4).Address & ";" & _
      Sheets(SN_COMB).Cells(ROW_START, COL_START + i - 1).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, COL_START + i - 1).Address & ")"
    'aufgerundet
    Sheets(SN_COMB).Cells(4, i + COL_START - 1).FormulaLocal = "=SUMMENPRODUKT(AUFRUNDEN(" & _
      Sheets(SN_COMB).Cells(ROW_START, 4).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 4).Address & ";0);" & _
      Sheets(SN_COMB).Cells(ROW_START, COL_START + i - 1).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, COL_START + i - 1).Address & ")"
    'abgerundet
    Sheets(SN_COMB).Cells(5, i + COL_START - 1).FormulaLocal = "=SUMMENPRODUKT(ABRUNDEN(" & _
      Sheets(SN_COMB).Cells(ROW_START, 4).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 4).Address & ";0);" & _
      Sheets(SN_COMB).Cells(ROW_START, COL_START + i - 1).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, COL_START + i - 1).Address & ")"
    'mathematisch gerundet
    Sheets(SN_COMB).Cells(6, i + COL_START - 1).FormulaLocal = "=SUMMENPRODUKT(RUNDEN(" & _
      Sheets(SN_COMB).Cells(ROW_START, 4).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, 4).Address & ";0);" & _
      Sheets(SN_COMB).Cells(ROW_START, COL_START + i - 1).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + imax - 1, COL_START + i - 1).Address & ")"
  Next
  
  'Schnittfolge Funktion einfügen, um das Ergebnis darzustellen
  For i = 1 To imax
    Sheets(SN_COMB).Cells(i + ROW_START - 1, 6).FormulaLocal = "=CuttingSequence(D" & CStr(i + 6) & ";" & _
      Sheets(SN_COMB).Cells(1, COL_START).Address & ":" & Sheets(SN_COMB).Cells(1, COL_START + itemsCount - 1).Address & ";" & _
      Sheets(SN_COMB).Cells(ROW_START + i - 1, COL_START).Address & ":" & Sheets(SN_COMB).Cells(ROW_START + i - 1, COL_START + itemsCount - 1).Address & ")"
  Next
  
  Application.ScreenUpdating = True
End Sub

Beispiel Sägeauftrag

Im Buch von Zimmermann/Stache wird ein Beispiel berechnet.

Sägeauftrag:

Rohstablängen von 6,2m mit 5 cm Anfangsstück und 15 cm Endstücken
Eine Schnittbreite muss nicht berücksichtigt werden: 0 mm

18 Stk à 1810 mm
150 Stk à 1740 mm
10 Stk à 1550 mm
100 Stk à 1340 mm

Um dieses nachzubauen, sind die Eingaben in den gelben Feldern ab H1 (Sägelängen) und H2 (Mengen) notwendig. Die Einstellungen zum Rohstab passieren im Tabellenblatt Grunddaten.

Danach reicht ein Klick auf den Button „Kombinationen erzeugen“, um alle Schnittkombinationen zu berechnen und anzuzeigen.

In diesem Beispiel erzeugt der Algorithmus 20 sinnvolle Schnittkombinationen.

Mathematisches Modell erstellen

Damit ist der erste Teil erledigt. Die Vorbereitungen für die eigentliche Optimierungsberechnung sind geschaffen. Jetzt müssen diese in ein mathematisches Modell überführt werden, damit der Solver in Excel die Simplex Methode anwenden kann.

Das mathematische Modell benötigt zuerst die Maximierungsfunktion. Basierend auf dem obigen Beispiel sieht die zugehörige Operations Research Aufgabe so aus:

Maximiere z = 5430•x1+5360•x2+5170• x3+4960•x4+5290•x5+5100•x6+4890•x7+4910•x8+4700•x9+4830•x10+5220•x11+5030•x12+4820•x13+4840•x14+5970•x15+5760•x16+5990•x17+5780•x18+5570•x19+5360•x20

Es müssen aber Nebenbedingungen einhalten werden, damit die richtigen Mengen erreicht werden. Deswegen gelten außerdem diese Nebenbedingungen:

3•x1+2•x2+3•x3+x4+x5+x6+x7+x8+x9+x10 <= 18

x2+2•x5+x6+x7+3•x11+2•x12+2•x13+x14+x15+x16 <= 150

x3+x6+2•x8+x9+x12+2•x14+x15+3•x17+2•x18+x19 <= 10

x4+x7+x9+x3•x10+x13+2•x15+3•x16+x17+2•x18+3•x19+4•x20 <= 100

Zusätzlich muss gelten, dass alle x-Werte >=0 sind, da vermutlich auch bei Ihnen keine negativen Mengen gesägt werden können.

Das Modell in Excel umsetzen

Damit der Solver arbeiten kann, braucht er das mathematische Modell umgesetzt in Excel Formeln. Hier hilft der Tabellenaufbau, den der Schnittkombinationen Algorithmus bereits erzeugt hat.

Maximierende Funktion z

Zuerst muss in einer Zelle die zu maximierende Funktion stehen.

In der Tabellenvorlage steht sie in der Zelle B2. Je nach Umfang der Sägeliste muss sich die Funktion an die Schnittwerte anpassen. Eine manuelle Eingabe ist daher nicht zu empfehlen.

Man kann aber gut erkennen, dass nur eine Multiplikation von zwei Spalten der Schnittkombinationen-Tabelle durchzuführen ist. Dafür gibt es in Excel die SUMMENPRODUKT Funktion. Sie benötigt als Parameter nur die beiden Wertebereiche.

Auch diese Arbeit nimmt der VBA Code beim Klicken von „Schnittkombinationen erzeugen“ ab.

Beispiel: Formel in Zelle B2

=SUMMENPRODUKT($D$7:$D$26;$B$7:$B$26)

Optimierungsparameter

Als nächstes muss auf den Tabellenblatt ein Bereich zur Verfügung stehen, wo der Solver die Optimierungsergebnisse eintragen kann. D. h. es muss nur ein leerer Bereich definiert werden.

In der Vorlage ist das die Spalte D unter „Simplex Ergebnis“.

Nebenbedingungen

Zuletzt muss dem Solver übermittelt werden, welche Nebenbedingungen zu berücksichtigen sind. Dafür wird auf der einen Seite die Sollmenge benötigt. Diese ist bereits durch die manuelle Eingabe vorhanden. Auf der anderen Seite muss der Solver die erreichte Menge auf Basis des Optimierungsergebnisses kennen.

Das kann auch über die SUMMENPRODUKT Formel berechnet werden.

SUMMENPRODUKT Formel zur Berechnung der erreichten Mengen

Auch hier nimmt die VBA Routine die Arbeit ab und trägt die SUMMENPRODUKT Formel passend für die Sägeliste ein.

Solver in Excel aktivieren

Der Solver steht in Excel als Add-In zur Verfügung. Das bedeutet, er muss aktiviert sein. Das lässt sich über die Excel Optionen einstellen.

Excel Optionen öffnen
Add-Ins auswählen
Solver aktivieren
Solver Dialog über die Ribbonleiste „Daten“ öffnen

Excel Optionen öffnen und Add-Ins auswählen
Solver aktivieren
Solver Dialog über die Ribbonleiste „Daten“ öffnen

Solver mit mathematischem Modell verbinden

Die Verbindung zwischen dem Modell und dem Solver erfolgt im Dialog des Solvers. Rufen Sie ihn also über die Ribbonleiste Daten auf.

Danach müssen die Felder und Bereiche entsprechend verknüpft werden. Was wo stehen muss, finden Sie im nachfolgenden Screenshot für das Beispiel.

Bereiche und Felder mit dem Solver verbinden

Als Lösungsmethode wird Simplex-LP ausgewählt. Jetzt reicht ein Klick auf Lösen, um Ergebnisse zu erhalten.

Ergebnisse auswerten

Der Solver führt jetzt die Simplex Methode durch und schreibt das Optimierungsergebnis in die Spalte D.

Im Beispiel werden

18 Stäbe der Schnittkombination Nr. 5
10 Stäbe der Schnittkombination Nr. 12
36,4 Stäbe der Schnittkombination Nr. 13 und
21,2 Stäbe der Schnittkombination Nr. 16

als optimal ermittelt.

Um das in einer lesbaren Form zu bekommen, zeigt die Spalte F das gleich in Kombination mit den einzelnen Schnittfolgen an.

18• ( 1•1810, 2•1740 )
10• ( 2•1740, 1•1550 )
36,4• ( 2•1740, 1•1340 )
21,2• ( 1•1740, 3•1340 )

Fazit

Mit ein wenig Programmierung lässt sich das eindimensionale Cutting Stock Problem komfortabel in Zusammenarbeit mit dem Excel Solver lösen. Um den Solver zu aktivieren, sind nur wenige Verknüpfungen notwendig. Eingabe müssen aber für jedes Verschnittproblem gemacht werden.

Sollmengen / Erreichte Mengen nach verschiedenen Rundungsverfahren

Man sieht auch, dass der Solver auch reelle Zahlen als Lösung berechnet. Das hilft beim Sägen nicht unbedingt weiter. Dann bleiben wieder Reste übrig.

Es ist zwar möglich, Rundungsverfahren zu nutzen, dann wird aber nicht immer die Sollmenge erreicht. Falls das kein Problem ist, haben Sie jetzt ein schnelles Werkzeug für Ihre Verschnittoptimierung und können Kosten- und Ressourcenpotenziale heben.

Download

Eindimensionales-Verschnittproblem.zip

enthält das Beispiel und den vollständigen VBA Quellcode des Cutting Stock Problems

Mehr zum Thema Verschnittoptimierung

Die Wirtschaftlichkeit beim der Verschnittoptimierung hängt von weiteren 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.

Links / Anhang

Buch Operations Research von Zimmermann/Stache, 2001, Auflage 10

Eindimensionales Zuschnittproblem auf wikipedia: https://de.wikipedia.org/wiki/Eindimensionales_Zuschnittproblem

Informationen zum Excel Solver

Technik und Coding