Schneiden stock Problem

Die Schneid Lager Problems ist ein NP-vollständiges Optimierungsproblem im Wesentlichen reduzierbar auf das Rucksack-Problem. Genauer gesagt ist es eine ganze Zahl lineare Programmierungsproblem. Es ergibt sich aus vielen Anwendungen in der Industrie. Stellen Sie sich vor, dass Sie in einer Papierfabrik zu arbeiten, und Sie haben eine Reihe von Papierrollen mit fester Breite noch zu schneiden, aber verschiedene Kunden möchten unterschiedliche Anzahl von Rollen verschiedener großen Breiten. Wie wollen Sie, um die Rollen geschnitten, so dass Sie den Abfall zu minimieren?

Nach Ansicht des Verbands der Europäischen Papierindustrie, im Jahr 2012 die 1.331 Papiermaschinen in der Region produziert einen Durchschnitt von 56 Mio. des Umsatzes je €. Spar auch Bruchteile von 1% ist daher signifikant.

Formulierung und Lösungsansätze

Die Standardformulierung für das Schneiden-Lager Problem beginnt mit einer Liste von m Bestellungen, die jeweils benötigt Stück. Wir bauen dann eine Liste aller möglichen Kombinationen von Schnittwunden, Zuordnen zu jedem Muster eine positive ganze Zahl repräsentierende Größe, wie lange jedes Muster verwendet werden soll. Der lineare Programm ganze Zahl ist dann:

wobei die Anzahl von Malen um wird im Muster und sind die Kosten der Muster. Die genaue Art der Mengenbeschränkungen können auf subtile Weise verschiedene mathematische Eigenschaften führen. Mengenbeschränkungen der obigen Formulierung sind Mindestbedingungen. Wenn die Objektiv minimiert die Anzahl der verwendeten Einzelteile und Master, wenn die Einschränkung für die zu fertigenden Größe durch Gleichheit ersetzt, wird es das Behälterproblem. Die allgemeinste Formulierung hat zweiseitige Einschränkungen:

Diese Formulierung gilt nicht nur für eindimensionale Probleme. Viele Variationen sind möglich, einschließlich einer, wo das Ziel ist, den Abfall zu minimieren, aber der Gesamtwert der erzeugten Produkte zu maximieren, so dass jede um einen anderen Wert haben.

Im Allgemeinen ist die Anzahl der möglichen Muster exponentiell als eine Funktion von m ist, die Anzahl der Aufträge. Als die Anzahl von Aufträgen zunimmt, kann es daher unpraktisch werden, um die mögliche Schnittmuster aufzuzählen.

Ein alternativer Ansatz verwendet verzögerte Spalten Generation. Diese Methode löst das Schneid Lager Problem, indem Sie mit nur wenigen Mustern. Er erzeugt zusätzliche Muster, wenn sie benötigt werden. Für den eindimensionalen Fall, werden die neuen Muster durch Lösen eines Hilfsoptimierungsproblem genannt Knapsackproblems mit dualen variablen Informationen aus dem linearen Programm eingeführt. Das Rucksackproblem hat gut bekannten Methoden, es zu lösen, wie zum Beispiel Branch and Bound und dynamische Programmierung. Die verzögerten Spaltengenerierungsverfahren können wesentlich effizienter als der ursprüngliche Ansatz, zumal die Größe des Problems wächst. Die Säule Generation Ansatz in Bezug auf die Schneid stock Problem angewandt wurde von Gilmore und Gomory in einer Reihe von Arbeiten in den 1960er Jahren veröffentlicht Pionierarbeit geleistet. Gilmore und Gomory hat gezeigt, dass dieser Ansatz ist garantiert, um die optimale Lösung zu konvergieren, ohne dass alle möglichen Mustern im Voraus aufzuzählen.

Eine Begrenzung der ursprünglichen Gilmore und Gomory Methode ist, dass sie nicht zu behandeln Vollständigkeit, so kann die Lösung Fraktionen enthalten, zB ein bestimmtes Muster sollte 3,67 Mal hergestellt werden. Rundung auf die nächste ganze Zahl oft nicht funktioniert, in dem Sinne, dass es möglicherweise zu einer suboptimalen Lösung und / oder Unter- oder Überproduktion von einigen der Aufträge führen. Diese Einschränkung wird in der modernen Algorithmen, die zur Optimalität sehr großer Instanzen des Problems kann zu überwinden.

Die Schneid Lager Problem ist oft hoch degenerierte, dadurch gekennzeichnet, dass mehrere Lösungen mit derselben Abfall möglich. Diese Entartung entsteht, weil es möglich ist, Gegenstände zu bewegen, die Schaffung neuer Muster, ohne dass die Abfälle. Dies führt zu einer ganzen Serie von verwandten Problemen, die mit einem anderen Kriterium betrifft, wie die folgenden:

  • Der minimale Muster Anzahl Problem: eine Mindest-Muster-count-Lösung unter den Mindest-Abfalllösungen zu finden. Dies ist ein sehr schwieriges Problem, selbst wenn der Abfall bekannt. Es gibt eine Vermutung, dass jede Gleichheit beschränkte eindimensionalen Beispiel mit n-Bestellungen zumindest eine minimale Abfalllösung mit nicht mehr als n + 1-Muster hat. Keine obere auf die Anzahl von Mustern ist entweder bekannt, gebunden werden Beispiele mit n + 5 bekannt.
  • Die minimale Stack Problem: Diese beschäftigt sich mit der Sequenzierung der Muster, um nicht zu viele teilweise fertiggestellten Aufträge jederzeit zu haben. Dies war ein offenes Problem, bis 2007, als ein effizienter Algorithmus, der auf dynamische Programmierung veröffentlicht.
  • Die Mindestzahl der Messerwechsel Problem: Dies betraf mit Sequenzierung und Permutation der Muster, um die Anzahl der Male die Schneidmesser bewegt werden müssen, zu minimieren ist. Dies ist ein Spezialfall der verallgemeinerten Vertreterproblem.

Illustration von eindimensionalen Schneid Lager Problem

Eine Papiermaschine kann eine unbegrenzte Anzahl von Mutterrollen, die jeweils 5600 mm Breite zu erzeugen. Die folgenden 13 Einzelteile müssen geschnitten werden:

Lösung

Es gibt 308 mögliche Muster für dieses kleine Beispiel. Die optimale Antwort erfordert 73 Mutterrollen und hat 0.401% Abfälle; sie kann rechnerisch gezeigt, dass in diesem Fall die minimale Anzahl von Mustern mit diesem Niveau von Abfällen ist 10. Es kann auch berechnet werden, dass 19 verschiedene solcher Lösungen bestehen, die jeweils mit 10 Mustern und einer Verschwendung von 0,401%, von denen eine solche Lösung unterhalb und in der Abbildung dargestellt:

Klassifikation

Cutting-Lager-Probleme können auf verschiedene Weise klassifiziert werden. Eine Möglichkeit ist die Dimensionalität des Schneid: Das obige Beispiel veranschaulicht ein eindimensionales Problem; anderen industriellen Anwendungen von 1D treten beim Schneiden von Rohren, Kabeln und Stahlstangen. Zweidimensionale Probleme werden Möbel, Kleidung und Glasproduktion begegnet. Nicht viele dreidimensionale Anwendungen mit Schneiden sind bekannt; jedoch die eng verwandte 3D-Packungsproblem hat viele industrielle Anwendungen, wie beispielsweise Verpackungs Gegenstände in Containern).

Cutting-Lager Problem in Papier, Film und Metallindustrie

Industrielle Anwendungen modern stock Probleme für hohe Produktionsvolumen ergeben sich insbesondere bei Grundmaterial wird in großen Rollen, die weiter in kleinere Einheiten geschnitten werden produziert. Dies wird beispielsweise durchgeführt in der Papier- und Kunststofffolienindustrie, aber auch in der Produktion von Flach Metalle wie Stahl oder Messing. Es gibt viele Varianten und zusätzliche Einschränkungen, die sich aus speziellen Produktionseinschränkungen aufgrund von Maschinen und Prozessgrenzen, Kundenanforderungen und Qualitätsfragen; Einige Beispiele sind:

  • Zweistufig, wobei die in der ersten Stufe erzeugte Rollen werden dann ein zweites Mal verarbeitet. Zum Beispiel werden alle Büromaterial in einem solchen Verfahren hergestellt. Die Komplikation ergibt sich, weil die Maschine in der zweiten Stufe geringer ist als die Primär. Effiziente Nutzung der beiden Stufen der Produktion wichtig ist und was ist effizient für die Primärstufe kann für die sekundäre ineffizient sein, was zu Kompromissen. Metallisierte Folie und Kunststoffextrusion auf Papier, sind weitere Beispiele für ein solches Verfahren.
  • Wickler Einschränkungen, wo die Schneideprozess hat physikalische oder logische Randbedingungen: eine sehr verbreitete Einschränkung ist, dass nur eine bestimmte Anzahl von Schlitzmessern verfügbar sind, so dass möglicher Muster sollte nicht mehr als eine maximale Anzahl von Walzen enthält. Weil Wickler Maschinen ist nicht standardisiert, sind sehr viele andere Einschränkungen auftreten.
  • Ein Beispiel einer Kundenanforderung ist, wenn eine bestimmte Bestellung kann nicht von einem der beiden Randpositionen erfüllt werden: Dies ist, weil die Ränder der Folie dazu neigen, größere Schwankungen in der Dicke haben und einige Anwendungen können sehr empfindlich gegenüber diesen.
  • Ein Beispiel für eine Frage der Qualität ist, wenn der Masterrolle enthält Mängel, die auf rund geschnitten werden müssen. Teure Materialien mit hohen Qualitätseigenschaften, wie photographisches Papier oder Tyvek müssen sorgfältig optimiert, so dass die verschwendete Fläche minimiert wird.
  • Multi-Maschine-Probleme entstehen, wenn Aufträge auf mehr als einer Maschine hergestellt werden, und diese Maschinen haben unterschiedliche Breiten. Im allgemeinen Verfügbarkeit von mehr als einem Master-Rollenbreite verbessert die Abfälle erheblich; in der Praxis jedoch zusätzliche Auftragssplitting Einschränkungen Möglicherweise müssen berücksichtigt werden.
  • Es gibt auch eine halbkontinuierliche Problem, wo die erzeugten Rollen müssen nicht den gleichen Durchmesser haben, sondern kann in einem Bereich variieren. Dies geschieht in der Regel mit Blatt Bestellungen. Dies wird manchmal als eine 1½ eindimensionales Problem bekannt. Diese Variante tritt auch bei der Herstellung von Wellpappe, wo es heißt, etwas verwirrend, die Wellpappenplanungsproblem.
  • In der Metallindustrie ein wesentlicher Unterschied ist, dass in der Regel die Mutterrollen werden zuvor hergestellt und im Wesentlichen voneinander unterscheiden. Somit gibt es Ähnlichkeiten mit der oben erwähnten Mehrmaschinenproblem. Die Anwesenheit von Längenänderungen erzeugt eine 2D-Problem, denn Abfälle können sowohl in Breitenrichtung und in Längsrichtung auf.

Anbieter von Software, die die Schneid Lager Problem für die Papierindustrie zu lösen sind: ABB-Konzerns, Greycon, Honeywell, und Tieto.
Ein cutstock Algorithmus für die Stahlindustrie wurde später von Robert Gongorra im Jahr 1998 formuliert und SONS wurde entwickelt für die Stahlindustrie Stahlverbrauch zu verbessern, Abfälle zu minimieren.

Cutting-Lager Problem in der Glasindustrie

Die Guillotine Problem ist ein Problem der Schneidglasscheiben in Rechtecke der angegebenen Größen mit nur Schnitte, die den ganzen Weg über jedes Blatt fortsetzen.

Das Sortiment Problem

Das verwandte Problem der Bestimmung, für den eindimensionalen Fall wird die beste Master-Größe, die gegebene Nachfrage wird als Zusammenstellung Problem bekannt.

Geschichte

Das Schneiden stock Problem wurde erstmals durch Kantorovich 1939 formulierte 1951 vor dem Computer wurde weithin verfügbar, LV Kantorovich und VA Zalgaller vorgeschlagene Lösung des Problems der sparsamen Umgang mit Material an der Schneidestufe mit Hilfe der linearen Programmierung. Die vorgeschlagene Technik wurde später genannt Column-Generation-Methode.

Software

  0   0
Vorherige Artikel Konkrete Nummer
Nächster Artikel Dot chinesischen Webseite

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha